Swift sorting algorithm implementation

2 Solutions Collect From Internet About “Swift sorting algorithm implementation”

Update: Swift is open source now, and in

one can clearly see that sorting a collection is done using introsort
with a maximum recursion depth of 2*floor(log(N)), and switches to
insertion sort for ranges with less than 20 elements.

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.

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.