Swift为其标准库实现了哪种排序算法？

Question

我想知道Swift的sort功能是如何实现的。它使用哪种排序算法-
它是mergesort，quicksort还是完全不同的东西？此功能提供的时序/复杂度保证是什么？

我无法在网上或官方文档中找到任何实现方式的迹象。

Answer 1

更新2：
正如我们在看到Sort.swift，sort()现在使用“修改timsort”在斯威夫特5
Timsort是

从混合排序和插入排序派生的混合稳定排序算法

在最坏的情况下，Timsort进行O（n log
n）比较来对n个元素的数组进行排序。在最好的情况下（发生在输入已被排序时），它以线性时间运行，这意味着它是一种自适应排序算法。

这意味着在Swift 5 中sort()碰巧是 稳定的排序
，但这仍然是实现细节。该MutableCollection.sort文件指出

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

另请参见sort（）在Swift 5中稳定吗？在Swift论坛中：

该算法只是在最近才稳定下来，以准备一个有保证的提议。

更新： Swift现在是开源的，并且在

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

可以看到使用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
*线程＃1：tid = 0x5a00，0x00000001001cb806 sort`sort。Swift.Bool + 454 at main.swift：22，队列='com.apple.main-thread'，停止原因=断点1.1
  *框架＃0：0x00000001001cb806 sort`sort。Swift.Bool + 454在main.swift：22
    框架＃1：0x00000001001cb62b用于Swift._Comparable。（Swift._Comparable.Self.Type）（Swift._Comparable.Self，Swift._Comparable.Self）-> Swift.Bool的sort_Protocol见证协议-MyStruct：Swift._Comparable + 27在main.swift：20
    框架＃2：0x00000001000f5a98 sort`Swift._partition（inout A，Swift.Range）-> A.Index + 3224
    框架＃3：0x00000001000f756a排序为Swift._introSortImpl（输入A，Swift.Range，Swift.Int）->（）+ 2138
    框架＃4：0x00000001000f6c01 sort`Swift._introSort（inout A，Swift.Range）->（）+ 1233
    框架5：0x00000001000fc47f sort`Swift.sort（inout A）->（）+ 607
    框架6：0x000000010013ea77 sort`Swift的部分应用转发器。（sort（inout Swift.Array）->（））。（closure＃1）+ 183
    框架＃7：0x000000010013eaf8部分将转发器的部分应用转发器从@callee_owned（@inout Swift.UnsafeMutableBufferPointer）->（@unowned（））到@callee_owned（@inout Swift.UnsafeMutableBufferPointer）->（@out（）） + 56
    框架＃8：0x0000000100046c4b sort`Swift.Array.withUnsafeMutableBufferPointer（inout Swift.Array）（（inout Swift.UnsafeMutableBufferPointer）-> B）-> B + 475
    框架＃9：0x00000001000fc5ad sort`Swift.sort（inout Swift.Array）->（）+ 157
    帧＃10：0x00000001001cb465在main.swift：29处排序top_level_code + 1237
    框架＃11：0x00000001001cbdca sort`main + 42 at main.swift：0
    框架＃12：0x00007fff8aa9a5fd libdyld.dylib`start + 1

然后

（lldb）bt
*线程＃1：tid = 0x5a00，0x00000001001cb806 sort`sort。Swift.Bool + 454 at main.swift：22，队列='com.apple.main-thread'，停止原因=断点1.1
  *框架＃0：0x00000001001cb806 sort`sort。Swift.Bool + 454在main.swift：22
    框架＃1：0x00000001001cb62b用于Swift._Comparable。（Swift._Comparable.Self.Type）（Swift._Comparable.Self，Swift._Comparable.Self）-> Swift.Bool的sort_Protocol见证协议-MyStruct：Swift._Comparable + 27在main.swift：20
    框架＃2：0x00000001000f449e sort`Swift._insertionSort（inout A，Swift.Range）->（）+ 2958
    帧＃3：0x00000001000f730e排序Swift._introSortImpl（inout A，Swift.Range，Swift.Int）->（）+ 1534
    框架＃4：0x00000001000f797d排序Swift._introSortImpl（inout A，Swift.Range，Swift.Int）->（）+ 3181
    帧＃5：0x00000001000f6c01 sort`Swift._introSort（inout A，Swift.Range）->（）+ 1233
    帧6：0x00000001000fc47f sort`Swift.sort（inout A）->（）+ 607
    框架＃7：0x000000010013ea77 sort`Swift的部分应用转发器。（sort（inout Swift.Array）->（））。（闭包＃1）+ 183
    框架＃8：0x000000010013eaf8部分将转发器的部分应用转发器从@callee_owned（@inout Swift.UnsafeMutableBufferPointer）->（@unowned（））到@callee_owned（@inout Swift.UnsafeMutableBufferPointer）->（@out（）） + 56
    框架＃9：0x0000000100046c4b排序swift.Array.withUnsafeMutableBufferPointer（inout Swift.Array）（（inout Swift.UnsafeMutableBufferPointer）-> B）-> B + 475
    框架＃10：0x00000001000fc5ad sort`Swift.sort（inout Swift.Array）->（）+ 157
    帧＃11：0x00000001001cb465在main.swift：29处排序top_level_code + 1237
    帧＃12：0x00000001001cbdca sort`main + 42 at main.swift：0
    框架＃13：0x00007fff8aa9a5fd libdyld.dylib`start + 1

这证实了Airspeed答案的猜想，即在较小范围内将
introsort 与 插入排序 结合使用。

如果数组的元素少于20个，则似乎仅使用插入排序。这 可能 表明从内省型转换为插入型的阈值为20。

当然，将来的实现可能会改变。