How to stable sort an array in swift?

Question

I've been using the sort() function but it mixes up the relative order.

This is how my code looks.

recipes.sort { 0ドル.skill.value <= 1ドル.skill.value }

Swift API says that:

The sorting algorithm is not stable. A nonstable sort may change the relative order of elements that compare equal.

How can I change this so that the relative order stays the same as before?

• Damien_The_Unbeliever: I was going to comment that this is referred to as a stable sort - but I see you've already quoted documentation that uses this phrase. Since you've encountered the term of art that expresses what you're looking for, why are you using different, vaguer phrasing for it? You're looking for a stable sort.
• demiculus: Sorry changing it.
• Martin R: Swift doesn't have a stable sort in the standard library. A quick Google search shows a similar question stackoverflow.com/questions/29322308/swift-stable-sort with some solutions, a Swift feature request: bugs.swift.org/browse/SR-306 and this article: airspeedvelocity.net/2016/01/10/writing-a-generic-stable-sort.
• Justin Meiners: Note that you should be using a strict inequality: <

Answer 1

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.

• Mackie Messer: @kelin your two edits don't actually work. Please undo or fix them! Thank you.
• Benjohn: Warning There seems to be a bug in the code here (corrected in Tom's answer that the stable offset order is used whenever areInIncreasingOrder(one.element, another.element) is false. It is necessary to resort to the stable offset if and only if !areInIncreasingOrder(one.element, another.element) && !areInIncreasingOrder(another.element, one.element) – ie, when the elements are "equal" with respect to the ordering areInIncreasingOrder. Apologies if I'm missing something and there is no fault – thank you!

Answer 2

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

• Benjohn: I think there is a bug with @leavez answer that your answer corrects. Their code reverts to the offset when !areInIncreasingOrder, but it should also check it with the arguments reversed so that stable offset is only used when the elements are "equal" with respect to areInIncreasingOrder.

Answer 3

let sortedArray = (recipes as NSArray).sortedArray(options: .stable, usingComparator: { (lhs, rhs) -> ComparisonResult in
 let lhs = (lhs as! Recipe)
 let rhs = (rhs as! Recipe)
 if lhs.skill.value == rhs.skill.value {
 return ComparisonResult.orderedSame
 } else if lhs.skill.value < rhs.skill.value {
 return ComparisonResult.orderedAscending
 } else {
 return ComparisonResult.orderedDescending
 }
})

Took from here: https://medium.com/@cocotutch/a-swift-sorting-problem-e0ebfc4e46d4

• devios1: It's really too bad that we have to revert to Objective-C for this. Why on earth would they choose an unstable sort as the default? Could they really not foresee such problems arising from that? Call me crazy but I will choose stability over performance any day, at least as the default, let alone only option.
• Zsolt Szatmari: They just assume that the developers knowing what they are doing. Should be a reasonable assumption... "stability" is a mathematical term here, do not mix up with the other meaning, safety, which does not apply here.

Answer 4

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).

• numist: I don't see anything that indicates that it will be guaranteed to be stable any day? In fact your quote says the very opposite with "a future version of Swift could ship an unstable algorithm".
• kelin: @numist, read the forum link.
• Shiki Suen: In Swift 6 it is guaranteed to be stable.

Answer 5

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

Answer 6

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

Answer 7

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.