What sorting algorithm does Swift implement for its standard library?

I am wondering how Swift's sort function is implemented. Which sorting algorithm does it use—is it a mergesort, quicksort, or something completely different? What are the timing/complexity guarantees provided by this function?

I can't find any indication of how it is implemented either online or in the official documentation.

Solution 1:

Update 2: As we can see in Sort.swift, sort() now uses a “modified timsort” in Swift 5. Timsort is a

... hybrid stable sorting algorithm, derived from merge sort and insertion sort ...

In the worst case, Timsort takes O(n log n) comparisons to sort an array of n elements. In the best case, which occurs when the input is already sorted, it runs in linear time, meaning that it is an adaptive sorting algorithm.

This means that sort() happens to be a stable sort in Swift 5, but that is still an implementation detail. The MutableCollection.sort documentation states that

The sorting algorithm is not guaranteed to be stable. A stable sort preserves the relative order of elements that compare equal.

See also Is sort() stable in Swift 5? in the Swift forum:

The algorithm was only recently made stable in preparation for a proposal to make it guaranteed as such.

Update: Swift is open source now, and in

https://github.com/apple/swift/blob/master/stdlib/public/core/Sort.swift

one can see that sorting a collection is done using introsort with a maximum recursion depth of 2*floor(log_2(N)). It switches to insertion sort for partitions with less than 20 elements, or to heapsort if the recursion depth is reached.

Old answer: Defining a custom Comparable structure and setting in breakpoint in <:

struct MyStruct : Comparable {
    let val : Int
}

func ==(x: MyStruct, y: MyStruct) -> Bool {
    println("\(x.val) ==  \(y.val)")
    return x.val == y.val
}
func <(x: MyStruct, y: MyStruct) -> Bool {
    println("\(x.val) < \(y.val)")
    return x.val < y.val // <--- SET BREAKPOINT HERE
}

var array = [MyStruct]()
for _ in 1 ... 30 {
    array.append(MyStruct(val: Int(arc4random_uniform(1000))))
}
sort(&array)

shows the following stack backtrace:

(lldb) bt
* thread #1: tid = 0x5a00, 0x00000001001cb806 sort`sort. Swift.Bool + 454 at main.swift:22, queue = 'com.apple.main-thread', stop reason = breakpoint 1.1
  * frame #0: 0x00000001001cb806 sort`sort. Swift.Bool + 454 at main.swift:22
    frame #1: 0x00000001001cb62b sort`protocol witness for Swift._Comparable.(Swift._Comparable.Self.Type)(Swift._Comparable.Self, Swift._Comparable.Self) -> Swift.Bool in conformance sort.MyStruct : Swift._Comparable + 27 at main.swift:20
    frame #2: 0x00000001000f5a98 sort`Swift._partition (inout A, Swift.Range) -> A.Index + 3224
    frame #3: 0x00000001000f756a sort`Swift._introSortImpl (inout A, Swift.Range, Swift.Int) -> () + 2138
    frame #4: 0x00000001000f6c01 sort`Swift._introSort (inout A, Swift.Range) -> () + 1233
    frame #5: 0x00000001000fc47f sort`Swift.sort (inout A) -> () + 607
    frame #6: 0x000000010013ea77 sort`partial apply forwarder for Swift.(sort (inout Swift.Array) -> ()).(closure #1) + 183
    frame #7: 0x000000010013eaf8 sort`partial apply forwarder for reabstraction thunk helper  from @callee_owned (@inout Swift.UnsafeMutableBufferPointer) -> (@unowned ()) to @callee_owned (@inout Swift.UnsafeMutableBufferPointer) -> (@out ()) + 56
    frame #8: 0x0000000100046c4b sort`Swift.Array.withUnsafeMutableBufferPointer (inout Swift.Array)((inout Swift.UnsafeMutableBufferPointer) -> B) -> B + 475
    frame #9: 0x00000001000fc5ad sort`Swift.sort (inout Swift.Array) -> () + 157
    frame #10: 0x00000001001cb465 sort`top_level_code + 1237 at main.swift:29
    frame #11: 0x00000001001cbdca sort`main + 42 at main.swift:0
    frame #12: 0x00007fff8aa9a5fd libdyld.dylib`start + 1

and later

(lldb) bt
* thread #1: tid = 0x5a00, 0x00000001001cb806 sort`sort. Swift.Bool + 454 at main.swift:22, queue = 'com.apple.main-thread', stop reason = breakpoint 1.1
  * frame #0: 0x00000001001cb806 sort`sort. Swift.Bool + 454 at main.swift:22
    frame #1: 0x00000001001cb62b sort`protocol witness for Swift._Comparable.(Swift._Comparable.Self.Type)(Swift._Comparable.Self, Swift._Comparable.Self) -> Swift.Bool in conformance sort.MyStruct : Swift._Comparable + 27 at main.swift:20
    frame #2: 0x00000001000f449e sort`Swift._insertionSort (inout A, Swift.Range) -> () + 2958
    frame #3: 0x00000001000f730e sort`Swift._introSortImpl (inout A, Swift.Range, Swift.Int) -> () + 1534
    frame #4: 0x00000001000f797d sort`Swift._introSortImpl (inout A, Swift.Range, Swift.Int) -> () + 3181
    frame #5: 0x00000001000f6c01 sort`Swift._introSort (inout A, Swift.Range) -> () + 1233
    frame #6: 0x00000001000fc47f sort`Swift.sort (inout A) -> () + 607
    frame #7: 0x000000010013ea77 sort`partial apply forwarder for Swift.(sort (inout Swift.Array) -> ()).(closure #1) + 183
    frame #8: 0x000000010013eaf8 sort`partial apply forwarder for reabstraction thunk helper  from @callee_owned (@inout Swift.UnsafeMutableBufferPointer) -> (@unowned ()) to @callee_owned (@inout Swift.UnsafeMutableBufferPointer) -> (@out ()) + 56
    frame #9: 0x0000000100046c4b sort`Swift.Array.withUnsafeMutableBufferPointer (inout Swift.Array)((inout Swift.UnsafeMutableBufferPointer) -> B) -> B + 475
    frame #10: 0x00000001000fc5ad sort`Swift.sort (inout Swift.Array) -> () + 157
    frame #11: 0x00000001001cb465 sort`top_level_code + 1237 at main.swift:29
    frame #12: 0x00000001001cbdca sort`main + 42 at main.swift:0
    frame #13: 0x00007fff8aa9a5fd libdyld.dylib`start + 1

This confirms the conjecture of Airspeed's answer that introsort is used in combination with insertion sort for the smaller ranges.

If the array has less than 20 elements then only insertion sort seems to be used. This could indicate that the threshold for switching from introsort to insertion sort is 20.

Of course the implementation might change in the future.

Solution 2:

Not a definitive answer, just guesswork – ~~only the Swift std lib dev team can tell and they haven’t~~ (scratch that, @martin-r shows how you can tell via the debugger! It's a hybrid introsort/insertion sort):

The docs for sort don’t state complexity. They do state it isn’t stable though (i.e. equal elements aren’t guaranteed to stay in their original order), which suggests it’s not a merge sort (which is usually stable).

There’s several functions in the Swift std lib that look like they’re there as helpers for other functions in the lib. There’s a partition function, which is a key building block for quick sorts. In the very early Swift betas, there used to be two sorts in addition to the non-brand-name one: quickSort and insertionSort.

The GNU implementation of the C++ std library sort uses a hybrid of an introsort (which is itself a hybrid of quicksort and heapsort) sometimes combined with an insertion sort. So it’s possible these two variants were originally implemented as building blocks for the actual sort feature.

quickSort and insertionSort disappeared in later betas – if sort were a best-case hybrid of both, there’d be little point calling one of them. partition is still there tho, presumably since it’s useful as a standalone function.

What sorting algorithm does Swift implement for its standard library?

Solution 1:

Solution 2:

Related

Recent Posts