如果每个数字连续出现两次，为什么内置的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 = eval(name)
    time = min(repeat(lambda: sorted(lst), number=1))
    print(f'{name}: {time*1e3 :5.1f} ms')

Answer 1

正如 btilly 在评论中提到的，这是由于 Timsort 排序算法的工作原理造成的。算法的详细描述是这里。

Timsort 通过识别已排序元素的运行来加速部分排序数组的操作。

跑步可以是 “升序”，表示非递减：

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

或“降序”，表示严格递减：

a0 > a1 > a2 > ...

请注意，一次运行始终至少为 2 长，除非我们从数组的 最后一个元素。

您的数组 a、b 和 c 每个仅包含一次运行。 数组 d 有 100 万次运行。

降序运行不能

>=

的原因是为了让排序稳定，即保持相等元素的顺序：

降序的定义很严格，因为主例程相反 原地下降运行，将下降运行转变为上升运行 跑步。逆转是通过明显的快速“交换元素从每个开始”来完成的 结束，并在中间收敛”的方法，并且如果 该切片包含任何相等的元素。使用严格的定义 降序确保降序运行包含不同的元素。