为何Python中已排序对象列表的排序耗时比未排序列表更长？

问题分析 #

你观察到的现象，本质是Timsort在处理带key函数的已排序列表时，内存缓存局部性变差，加上对有序元组序列的额外检查开销，导致总耗时超过未排序列表。具体原因可以拆分为以下几点：

1. key函数带来的元组列表开销 #

当使用key参数调用sorted()时，Python会先为每个元素计算key值，生成一个由(key_value, original_object)组成的元组列表，再对这个元组列表排序。这个过程本身就比直接排序原生浮点数多了元组创建和属性访问的额外开销——这也是测试中对象列表排序整体比浮点数慢的核心原因。

2. Timsort对有序序列的处理差异 #

对于原生浮点数的有序列表，Timsort能快速识别出这是一个完整的有序run（连续有序片段），仅需O(n)时间完成遍历确认，几乎不需要交换或合并操作。但对于元组组成的有序列表：

• Timsort需要遍历整个元组列表来确认其有序性，而元组的内存布局比原生浮点数更分散，导致CPU缓存命中率降低，每个元素的访问开销被放大；
• 相反，未排序的元组列表会被Timsort拆分成多个小run，合并这些小run时，元素的内存访问更集中，缓存利用率更高，抵消了部分排序算法O(nlogn)的开销。

3. 稳定排序的隐性检查 #

Timsort是稳定排序算法，即使你的测试数据中key值几乎唯一，它在处理有序序列时仍会额外检查相邻元素的key是否相等（以保证原顺序）。这部分检查在元组列表上的开销，比在原生浮点数列表上更明显。

验证方法（可选） #

如果预计算key值，再基于索引排序，就能消除重复计算key的开销，同时优化内存布局，已排序列表的排序耗时会大幅降低：

import random
import time

class C:
    def __init__(self, x):
        self.x = x

random_nbrs = [random.random() for _ in range(20_000_000)]
objects = [C(e) for e in random_nbrs]
# 预计算所有key值
keys = [obj.x for obj in objects]

# 基于预计算key排序索引
t0 = time.time()
indices = sorted(range(len(objects)), key=lambda i: keys[i])
y = [objects[i] for i in indices]
print("3. Sorting with precomputed keys took {:.2f} seconds".format(time.time() - t0))

t0 = time.time()
indices_sorted = sorted(range(len(y)), key=lambda i: keys[indices[i]])
z = [y[i] for i in indices_sorted]
print("4. Sorting sorted list with precomputed keys took {:.2f} seconds".format(time.time() - t0))

内容的提问来源于stack exchange，提问作者A.P.