python 内置 sorted() 使用 timsort 算法，其性能高度依赖输入中“自然有序段”（runs）的数量；当降序序列中存在重复相邻元素时，timsort 无法将其识别为单个降序 run，导致 run 数量暴增、合并开销剧增，从而大幅降低排序速度。
python 内置 sorted() 使用 timsort 算法，其性能高度依赖输入中“自然有序段”（runs）的数量；当降序序列中存在重复相邻元素时，timsort 无法将其识别为单个降序 run，导致 run 数量暴增、合并开销剧增，从而大幅降低排序速度。
Timsort 是 Python 的默认稳定排序算法（自 2.3 起启用），它并非简单地套用归并或插入排序，而是专为真实世界中部分有序数据设计的混合策略：它先扫描数组，识别出尽可能长的“单调 run”，再将这些 runs 归并成最终有序结果。这一机制让 Timsort 在处理已排序、近似排序或含多个升序块的数据时表现极佳（接近 O(n) 时间复杂度）。
关键在于 Timsort 对 run 的定义极为严格：
- 升序 run：满足 a[i]
- 降序 run：必须满足 a[i] > a[i+1] 的最长严格递减子序列（不允许相等）。
该设计并非疏忽，而是出于稳定性（stability） 的硬性要求。Timsort 在发现降序 run 后，会就地反转（in-place reverse）使其变为升序，再参与后续归并。若允许 >=，则反转操作会打乱相等元素的原始相对顺序（例如 [2, 2, 1] 反转为 [1, 2, 2]，两个 2 的位置被交换），破坏稳定性。因此，仅当元素严格递减时，才被视为一个降序 run。
现在看问题中的四组数据：
n = 2_000_000 a = [i // 1 for i in range(n)] # [0,1,2,...,1999999] → 1 个升序 run b = [i // 2 for i in range(n)] # [0,0,1,1,2,2,...] → 1 个升序 run（因允许 ） d = b[::-1] # [999999,...,2,2,1,1,0,0] → 每对相等数中断降序！
数组 d 的末尾是 ..., 2, 2, 1, 1, 0, 0。由于 2 == 2 不满足 >, Timsort 在第一个 2 处结束上一 run，并从第二个 2 开始新 run —— 实际上，d 被切分为约 1,000,000 个长度为 2 的降序 run（如 [2,2] 不合法，但 [2] 单元素不构成 run，故实际按 [2,2] 前半截断，形成大量极短 run）。大量短 run 导致：
- 更多 run 元信息需存储与管理；
- 归并阶段需执行远超必要的多次小规模归并；
- 缓存局部性变差，内存访问效率下降。
这正是 d 耗时（110.9 ms）远超 a/b/c（~35 ms）的根本原因——不是数据“更乱”，而是 run 结构被恶意“碎片化”。
✅ 验证示例（简化的 run 计数模拟）：
def count_runs(lst):
if not lst: return 0
runs = 1
i = 0
while i lst[i+1]:
while i + 1 lst[i+1]:
i += 1
else:
i += 1 # 单元素或相等中断，新 run
runs += 1
i += 1
return runs
print(count_runs(list(range(1000)))) # ≈ 1
print(count_runs([i//2 for i in range(1000)])) # ≈ 1（升序 run）
print(count_runs(list(range(1000))[::-1])) # ≈ 1（严格降序）
print(count_runs(([i//2 for i in range(1000)])[::-1])) # ≈ 500（大量双元素 run）
⚠️ 注意事项与最佳实践：
- 此现象在 Python 3.11+ 的 Powersort（Timsort 改进版）中依然存在，因其保留了相同的 run 检测逻辑；
- 若业务场景需频繁排序含重复降序片段的数据，可考虑预处理（如添加微小扰动保持严格性，但慎用——影响精度与稳定性）；
- 更推荐的方案是：确认是否真需 sorted() —— 若仅需 Top-K 或分位数，使用 heapq.nlargest() 或 numpy.partition() 效率更高；
- 性能调优时，永远以 timeit 多次采样 + min() 为准，避免单次测量噪声。
总之，Timsort 的卓越性能源于对现实数据模式的深刻洞察，而其 run 定义的“严苛”恰恰是稳定性和工程实用性的精妙平衡。理解 run 的生成逻辑，是高效驾驭 Python 排序能力的关键一步。
