Menu
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.
320
Swift uses Introsort. Looking at the source code we see that the chosen pivot is the first element. The wikipedia page on Introsort says: (...), one of the critical operations is choosing the pivot: the element around which the list is partitioned.
Like the insertion sort it is based on, library sort is a comparison sort; however, it was shown to have a high probability of running in O(n log n) time (comparable to quicksort), rather than an insertion sort's O(n2).
Bubble sort is a very basic sorting algorithm. It is used by starting at the beginning of an array and comparing the first couple elements. The elements are only swapped if the first element has a greater value than the second element.
Quicksort. Quicksort is one of the most efficient sorting algorithms, and this makes of it one of the most used as well. The first thing to do is to select a pivot number, this number will separate the data, on its left are the numbers smaller than it and the greater numbers on the right.
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
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.
124
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.
43
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
