为什么对于连续下降的数字列表，内置sorted()会更慢？

Question

我对四个相似的列表进行了排序。列表 d 的排序时间总是比其他列表要长得多，而其他列表的排序时间差不多：

a:  33.5 ms
b:  33.4 ms
c:  36.4 ms
d: 110.9 ms

这是为什么呢？

测试脚本（在线尝试这个！）:

from timeit import repeat

n = 2_000_000
a = [i // 1 for i in range(n)]  # [0, 1, 2, 3, ..., 1_999_999]
b = [i // 2 for i in range(n)]  # [0, 0, 1, 1, 2, 2, ..., 999_999]
c = a[::-1]                     # [1_999_999, ..., 3, 2, 1, 0]
d = b[::-1]                     # [999_999, ..., 2, 2, 1, 1, 0, 0]

for name in 'abcd':
    lst = globals()[name]
    time = min(repeat(lambda: sorted(lst), number=1))
    print(f'{name}: {time*1e3 :5.1f} ms')

Answer 1

正如 @jpa 的 回答 所解释的，a、b 和 c 只有一个“运行”，而 d 有一百万个。我们可以通过比较的次数来看看这个效果：

a:  1999999 comparisons, 1.000 per element
b:  1999999 comparisons, 1.000 per element
c:  1999999 comparisons, 1.000 per element
d: 10710650 comparisons, 5.355 per element

一个长的运行意味着我们只需要比较每对相邻的元素一次，仅此而已。对于 n 个元素来说，这就是 n-1 次比较。

因为 a 和 b 是升序排列的，所以它们已经排好序了，不需要再做任何处理。c 是降序的，只需将它反转一下，也就完成了。

对于 d，两个元素的运行首先会通过二进制插入排序合并成 32 到 64 个元素的运行。然后这些更长的运行会不断合并成更大更大的运行，直到整个列表都排好序。

我尝试了不同的 n 值。对于 d，每个元素的比较次数大约在 5 次左右，随着 n 增加到 2 的幂次时，比较次数上升到大约 5.3，然后又降到大约 4.7。一般来说，d 需要 O(n) 次比较。它不需要 n log n 次比较，因为合并时使用了“跳跃”（一种指数搜索），在这种情况下只需要对数级别的比较。因此，与普通的归并排序不同，这里的比较次数的递归关系不是 T(n) = 2T(n/2) + n，而是 T(n) = 2T(n/2) + log(n)，这也是 O(n)。

不过，运行时间并不是 O(n)，因为仍然需要 n log n 次元素的移动。但这属于底层操作，相对比较快，和 O(n) 的慢比较相比，速度要快很多。如果你测量不同 n 值的时间，你可能会觉得它是 O(n) 的时间。

用于计数的脚本（在线尝试这个！）：

n = 2_000_000
a = [i // 1 for i in range(n)]
b = [i // 2 for i in range(n)]
c = a[::-1]
d = b[::-1]

class Int:
    def __init__(self, value):
        self.value = value
    def __lt__(self, other):
        global comparisons
        comparisons += 1
        return self.value < other.value

for name in 'abcd':
    lst = globals()[name]
    comparisons = 0
    sorted(map(Int, lst))
    print(f'{name}: {comparisons} comparisons, {comparisons/len(lst) :5.3f} per element')

Answer 2

正如btilly和Amadan在评论中提到的，这个问题和Timsort排序算法的工作原理有关。关于这个算法的详细描述可以在这里找到。

Timsort通过识别已经排序的元素序列来加快对部分排序数组的操作。

一个序列可以是“升序”的，也就是不减少：

a0 <= a1 <= a2 <= ...

或者是“降序”的，也就是严格减少：

a0 > a1 > a2 > ...

需要注意的是，一个序列至少要有两个元素，除非我们从数组的最后一个元素开始。

你的数组a、b和c每个都只有一个序列。而数组d有100万个序列。

降序序列不能用>=的原因是为了保持排序的稳定性，也就是说要保持相等元素的顺序：

降序的定义是严格的，因为主要的排序过程会将降序序列就地反转，变成升序序列。反转是通过一种简单快速的方法完成的，即“从两端开始交换元素，向中间靠拢”，如果这个片段中有相等的元素，这样做可能会破坏稳定性。使用严格的降序定义可以确保降序序列中的元素是不同的。

Python 3.11对timsort进行了稍微改进的版本，有时被称为powersort，但它使用相同的序列检测方法，因此性能是一样的。