如果使用IntroSort算法，Swift Array.sort()如何比元组更快地对整数进行排序？Swift是否对整数进行了不同的排序？

Question

我一直在挑选和探索Swift array的排序函数，我惊讶地发现，对一个包含500,000个整数的数组进行就地排序比对一个包含500,000个元组的数组进行排序要快得多(快5倍)。我对这一发现感到惊讶，因为在询问了之前关于Stack overflow的问题并深入研究了Swift开源之后，Swift似乎只使用了introSort()作为其排序算法。我试图解析代码，看看它是否以任何不同/特殊的方式处理整数排序，但我找不到任何东西。时间复杂度方面，IntroSort()执行NlogN、平均和最坏情况，所以我的元组排序和整数排序的行为应该是一样的。如果你做了数学计算，5倍的速度开始看起来像是线性对NlogN时间复杂度。

这让我思考，也许Swift正在使用线性时间整数排序算法来处理整数排序，也许我只是错过了它。现在我不是整数排序方面的专家，但是看起来整数排序算法最可行的候选者是文件孔排序、countingSort和RadixSort。我马上就排除了基数排序，因为它的时间复杂度是O(wn)，其中w是word/int大小。这意味着通用排序中的(logN)项需要大于w，这就需要我们对一个大得离谱的列表进行排序。看一下int排序和tuple排序的性能，我推断基数排序不可能在这里使用。

按照消除的顺序，剩下的是CountingSort排序和归档排序。它们的最坏情况都是O(N + k)，其中N是元素的数量，k是值的范围。因此，为了确定Swift的算法是否是这些排序中的一种，我认为将具有较小键值的500,000个整数的排序与具有大量键的500,000个整数的排序进行比较就足够了。对于第一个数组，我选择了键范围1,500,000。对于第二个数组，我选择了键范围1，6,000,500,000。如果第二个数组使用计数排序或归类排序(只要计算一下就知道了)，那么第二个数组的排序时间会比第一个数组长得多。令我惊讶的是，表演是完全一样的！下面是我的示例代码和性能结果：

 func testTupleSortVsIntegerSort()
    {
        var intArray = [Int]()
        for value in 1..<500000 {
            intArray.append(value)
        }

        var tupleArray = intArray.map{($0, "sentinelValue")}
        intArray.shuffle()
        tupleArray.shuffle()

        var startTime = CFAbsoluteTimeGetCurrent()
        intArray.sort()
        var endTime = CFAbsoluteTimeGetCurrent()
        print("Integer sort took \(endTime - startTime) seconds")

        startTime = CFAbsoluteTimeGetCurrent()
        tupleArray.sort {
            return $0.0 < $1.0
        }
        endTime = CFAbsoluteTimeGetCurrent()
        print("Tuple sort took \(endTime - startTime) seconds")

    }

    func testIntegerSortWithSmallKeyRangeVsVeryLargeKeyRange()
    {

        var intArrayWithSmallKeys = [Int]()
        for value in 1..<500000 {
            intArrayWithSmallKeys.append(value)
        }

        var intArrayWithLargeKeys: [Int] = intArrayWithSmallKeys.map {
            if $0 < 250000 {
                return $0
            } else if $0 < 350000 {
                return $0 + 50000000
            } else {
                return $0 + 6000000000
            }
        }

        intArrayWithSmallKeys.shuffle()
        intArrayWithLargeKeys.shuffle()

        var startTime = CFAbsoluteTimeGetCurrent()
        intArrayWithSmallKeys.sort()
        var endTime = CFAbsoluteTimeGetCurrent()
        print("Integer sort with small keys took \(endTime - startTime) seconds")

        startTime = CFAbsoluteTimeGetCurrent()
        intArrayWithLargeKeys.sort()
        endTime = CFAbsoluteTimeGetCurrent()
        print("Integer sort with large keys took \(endTime - startTime) seconds")

    }

Test Case '-[ColorExtractorTests.GeneralPerformanceTest testTupleSortVsIntegerSort]' started.
Integer sort took 0.659438014030457 seconds
Tuple sort took 3.40226799249649 seconds

Test Case '-[ColorExtractorTests.GeneralPerformanceTest testIntegerSortWithSmallKeyRangeVsVeryLargeKeyRange]' started.
Integer sort with small keys took 0.665884971618652 seconds
Integer sort with large keys took 0.669007003307343 seconds

这里发生什么事情？有没有我不知道的神奇的整数排序算法？我对这些排序算法的理解是错误的，还是我的分析中有一些缺陷？

Answer 1

请参阅Martin R和Honza Denjar对问题的回复。这些insites帮助我意识到发生了什么。您排序的数据会严重影响性能，而不仅仅是排序的元素数量。有时这一课会被遗忘。