Swift 使用哪种通用排序算法？它在排序数据上表现不佳

我一直在挑选和探索 Swift 标准库sort()其函数为Array类型。令我惊讶的是，我注意到它在已经排序的数据上表现不佳。

对数组进行排序Int打乱顺序似乎比对已经排序的同一个数组进行排序快 5 倍。对已打乱顺序的对象数组进行排序比对已按排序顺序的相同对象进行排序大约快 4 倍（对对象数组进行排序与Int我确信数组使用不同的算法，所以我对两者进行了排序以消除偏差）。

结果如下：

Shuffled Int array sort time: 1.3961209654808
Shuffled ColorObject array sort time: 3.14633798599243
NOnshuffled Int array sort time: 7.34714204072952
NOnshuffled ColorObject array sort time: 10.9310839772224

以下是我的代码供参考：

class ElapsedTimer {

    let startTime: CFAbsoluteTime
    var endTime: CFAbsoluteTime?

    init() {
        startTime = CFAbsoluteTimeGetCurrent()
    }

    func stop() -> CFAbsoluteTime {
        endTime = CFAbsoluteTimeGetCurrent()
        return duration!
    }

    var duration: CFAbsoluteTime? {
        if let endTime = endTime {
            return endTime - startTime
        } else {
            return nil
        }
    }
}

public class CountedColor {
    public private(set) var count: Int
    public private(set) var color: UIColor

    public init(color: UIColor, colorCount: Int) {
        self.count = colorCount
        self.color = color
    }
}

var distributedIntArray = [Int]()

for value in 1..<1000000 {
    distributedIntArray.append(value)
}

var distributedCountedColorArray = distributedIntArray.map{ CountedColor(color: UIColor.white, colorCount: $0) }

distributedCountedColorArray.shuffle()
distributedIntArray.shuffle()

var timer = ElapsedTimer()
distributedIntArray.sort()
print("Shuffled Int array sort time: \(timer.stop())")
timer = ElapsedTimer()

distributedCountedColorArray.sort{ return $0.count < $1.count }
print("Shuffled Color array sort time: \(timer.stop())")
timer = ElapsedTimer()

distributedIntArray.sort()
print("NOnshuffled Int array sort time: \(timer.stop())")
timer = ElapsedTimer()

distributedCountedColorArray.sort{ return $0.count < $1.count }
print("Non shuffled Color array sort time: \(timer.stop())")

我的阵列shuffle()方法是从这个帖子 https://stackoverflow.com/questions/37843647/shuffle-array-swift-3/37843901. My ElapsedTimer简单地包装和使用CACurrentMediaTime()功能。

我的问题是为什么我会看到这种行为？特别是当我对对象数组进行排序时，它肯定应该使用通用排序。 Swift 使用哪种通用排序算法？它肯定不可能是像归并排序那样最坏情况和平均情况相同的情况。

斯威夫特使用介绍 https://en.wikipedia.org/wiki/Introsort。看着源代码 https://github.com/apple/swift/blob/master/stdlib/public/core/Sort.swift.gyb我们看到所选的主元是第一个元素。 Introsort 的维基百科页面说道：

(...)，关键操作之一是选择枢轴： 列表围绕其进行分区的元素。最简单的枢轴 选择算法是取第一个或最后一个元素 列表作为枢轴，导致排序或排序的情况下表现不佳 几乎排序的输入。

因此，在给定实现选择的情况下，完全可以预测，Swift 的排序性能对于已排序的输入来说是最差的。

我为那些想要轻松重现OP声明的人建立了一个完整的基准：https://github.com/lemire/Code-used-on-Daniel-Lemire-s-blog/tree/master/extra/swift/sort https://github.com/lemire/Code-used-on-Daniel-Lemire-s-blog/tree/master/extra/swift/sort

作为参考，GNU ISO C++ 标准库使用中位数为 3 的主元（根据stl_algo.h标题）。