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

Question

我一直在 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() 方法是从 this post 中提取的.我的 ElapsedTimer 只是包装并使用 CACurrentMediaTime() 函数。

我的问题是为什么我会看到这种行为？特别是当我正在对肯定应该使用通用排序的对象数组进行排序时。 swift 使用什么样的通用排序算法？肯定不可能像mergeSort那样最坏情况和平均情况一样。

Answer 1

swift 使用 Introsort .看着 source code我们看到选择的枢轴是第一个元素。 Introsort 上的维基百科页面说:

(...), one of the critical operations is choosing the pivot: the element around which the list is partitioned. The simplest pivot selection algorithm is to take the first or the last element of the list as the pivot, causing poor behavior for the case of sorted or nearly sorted input.

因此完全可以预见，考虑到实现选择，Swift 的排序性能对于已排序的输入是最差的。

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

作为引用，GNU ISO C++ 标准库使用中位数为 3 的基准(根据 STL_algo.h header )。