How to stable sort an array in swift?

The implementation below just work like the sorted method in the standard library, without additional limit.

extension RandomAccessCollection {

    /// return a sorted collection
    /// this use a stable sort algorithm
    ///
    /// - Parameter areInIncreasingOrder: return nil when two element are equal
    /// - Returns: the sorted collection
    public func stableSorted(by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows -> [Element] {

        let sorted = try enumerated().sorted { (one, another) -> Bool in
            if try areInIncreasingOrder(one.element, another.element) {
                return true
            } else {
                return one.offset < another.offset
            }
        }
        return sorted.map { $0.element }
    }
}

A stable sort needs to preserve the original order. So we give every element a weight of order besides its value, the index, then the original sort method will just work, as there will never be 2 equal elements.

I appreciate the elegance of leavez's answer. I adapted it to have the same signature as Sequence.sorted(by:):

extension Sequence {
  func stableSorted(
    by areInIncreasingOrder: (Element, Element) throws -> Bool)
    rethrows -> [Element]
  {
    return try enumerated()
      .sorted { a, b -> Bool in
        try areInIncreasingOrder(a.element, b.element) ||
          (a.offset < b.offset && !areInIncreasingOrder(b.element, a.element))
      }
      .map { $0.element }
  }
}