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 }
  }
}

In Swift 5 sort() uses stable implementation and soon it will become officially guaranted to be stable.

Update: In Swift 6 it is guaranteed to be stable.

From Swift forums:

...
On the other hand, the actual implementation calls

/// Sorts the elements of this buffer according to `areInIncreasingOrder`,
/// using a stable, adaptive merge sort.
///
/// The adaptive algorithm used is Timsort, modified to perform a straight
/// merge of the elements using a temporary buffer.
@inlinable
public mutating func _stableSortImpl(
    by areInIncreasingOrder: (Element, Element) throws -> Bool
) rethrows { ... }

And

If I recall, sort() is currently stable, but it is not yet guaranteed to be stable (meaning, the fact that it is stable is currently an implementation detail, and a future version of Swift could ship an unstable algorithm instead).

I use this wrapper

extension Array where Element: Comparable, Element: AnyObject {
    public func stableSorted() -> [Element] {
        let array = self as NSArray
        let result = array.sortedArray(options: .stable) { (left, right) -> ComparisonResult in
            let left = left as! Element
            let right = right as! Element
            if left < right {
                return ComparisonResult.orderedAscending
            }
            if left > right {
                return ComparisonResult.orderedDescending
            }
            return ComparisonResult.orderedSame
        }
        return result as! [Element]
    }
    public func stableReversed() -> [Element] {
        let array = self as NSArray
        let result = array.sortedArray(options: .stable) { (left, right) -> ComparisonResult in
            let left = left as! Element
            let right = right as! Element
            if left > right {
                return ComparisonResult.orderedAscending
            }
            if left < right {
                return ComparisonResult.orderedDescending
            }
            return ComparisonResult.orderedSame
        }
        return result as! [Element]
    }
}

I appreciate the elegance of Tom's answer. Harking back to my Perl days I've reworked it to use ComparisonResult and the spaceship (<=>) operator:

extension Sequence {
    func sorted(with comparator: (Element, Element) throws -> ComparisonResult) rethrows -> [Element]
    {
        return try enumerated()
            .sorted { (try comparator($0.element, $1.element) || $0.offset <=> $1.offset) == .orderedAscending }
            .map { $0.element }
    }
}

extension Comparable {
    static func <=> (lhs: Self, rhs: Self) -> ComparisonResult {
        if lhs < rhs { return .orderedAscending }
        if lhs > rhs { return .orderedDescending }
        return .orderedSame
    }
}

extension ComparisonResult {
    static func || (lhs: Self, rhs: @autoclosure () -> Self) -> ComparisonResult {
        if lhs == .orderedSame {
            return rhs()
        }
        return lhs
    }
}

The existence of this question thread made me misunderstood in these years, believing the "lack of stable-sort" in Swift.

However, at least Swift 6 always sort things stably:

The sorting algorithm is guaranteed to be stable. A stable sort preserves the relative order of elements for which areInIncreasingOrder does not establish an order.

Still, if there's an early version of Swift 5 has lack of this support, please leave me a comment.