Swift 为其标准库实现了什么排序算法？

我想知道斯威夫特怎么样sort功能已实现。它使用哪种排序算法——是合并排序、快速排序还是完全不同的算法？该函数提供的时序/复杂性保证是什么？

我在网上或官方文档中找不到任何关于它是如何实现的指示。

更新2：正如我们所看到的快速排序 https://github.com/apple/swift/blob/master/stdlib/public/core/Sort.swift, sort()现在在 Swift 5 中使用“修改的 timsort”。Timsort https://en.wikipedia.org/wiki/Timsort is a

...混合稳定排序算法，源自合并排序和插入排序...

在最坏的情况下，Timsort 需要 O(n log n) 次比较来对 n 个元素的数组进行排序。在最好的情况下，当输入已经排序时，它会以线性时间运行，这意味着它是一种自适应排序算法。

这意味着sort()恰好是一个稳定排序在 Swift 5 中，但这仍然是一个实现细节。这MutableCollection.sort https://developer.apple.com/documentation/swift/mutablecollection/2802575-sort文件指出

不保证排序算法稳定。稳定排序保留比较相等的元素的相对顺序。

也可以看看sort() 在 Swift 5 中稳定吗？ https://forums.swift.org/t/is-sort-stable-in-swift-5/21297在 Swift 论坛中：

该算法最近才变得稳定，为保证其稳定性的提案做准备。

Update:Swift 现在是开源的，并且在

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

人们可以看到对集合进行排序是使用介绍 https://en.wikipedia.org/wiki/Introsort最大递归深度为 2*floor(log_2(N))。对于少于 20 个元素的分区，它切换到插入排序，或者切换到堆排序 如果达到递归深度。

旧答案：定义自定义Comparable结构和断点设置<:

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)

显示以下堆栈回溯：

(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
  

然后

(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

  

这证实了猜想空速的答案 https://stackoverflow.com/a/27677628/1187415 that 介绍用来 结合插入排序对于较小的范围。

如果数组的元素少于 20 个，则似乎仅使用插入排序。 这could表示从 introsort 切换到的阈值 插入排序是20。

当然，将来的实现可能会发生变化。