Python 的 sorted() 函数基于 Timsort 算法，其性能高度依赖输入中“自然有序段（runs）”的数量；当降序序列中存在相邻相等元素时，Timsort 无法将其识别为单个降序 run，导致 run 数量激增，引发显著性能下降。
python 的 `sorted()` 函数基于 timsort 算法，其性能高度依赖输入中“自然有序段（runs）”的数量；当降序序列中存在相邻相等元素时，timsort 无法将其识别为单个降序 run，导致 run 数量激增，引发显著性能下降。
Timsort 是 Python 内置排序算法（自 2.3 版起），它并非单纯依赖比较的通用排序器，而是一种自适应、稳定、混合型排序算法，核心思想是：高效识别并利用输入数据中已存在的局部有序性（即“runs”），再通过归并策略合并这些 runs。
根据 Timsort 的定义，一个 run 必须满足以下之一：
- 升序 run：a[0] ≤ a[1] ≤ a[2] ≤ ...（允许相等，即非严格递增）；
- 降序 run：a[0] > a[1] > a[2] > ...（必须严格递减，不允许相等）。
⚠️ 关键限制在于：降序 run 不允许包含相等元素。这是为保障排序稳定性（stability）所作的强制设计——Timsort 在发现降序 run 后会原地反转它（O(k) 时间），而若 run 中存在重复值（如 [2, 2, 1, 1]），直接反转将破坏相等元素的原始相对顺序（例如两个 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, ..., 999999] → 1 个升序 run（因允许相等） c = a[::-1] # [1999999, ..., 1, 0] → 1 个严格降序 run（无重复） d = b[::-1] # [999999, ..., 2, 2, 1, 1, 0, 0] → 每对相等数构成“断点”
对于 d，由于反转后形如 [..., 3, 3, 2, 2, 1, 1, 0, 0]，任意相邻相等元素（如 2, 2）都会中断降序 run。Timsort 将每个 x, x 视为“无法延伸的降序段”，被迫将其拆分为长度为 2 的独立 run（实际最小 run 长度受 minrun 机制约束，但此处因严格降序要求失效，最终生成约 1,000,000 个 runs）。相比之下，a/b/c 均仅含 1 个 run，归并开销极小；而 d 需归并百万级 runs，时间复杂度从接近 O(n) 退化至 O(n log n)，且常数因子剧增——这正是 d 耗时达 110.9 ms（其余仅 ~35 ms）的根本原因。
✅ 验证示例（简化版 run 计数逻辑）：
def count_timsort_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_timsort_runs(list(range(1000))[::-1])) # ≈ 1（严格降序）
print(count_timsort_runs([x//2 for x in range(1000)][::-1])) # ≈ 500（每对相同数截断）
? 注意事项与实践建议：
- 勿将“看似有序”等同于“Timsort 友好”：降序 + 重复 = 性能陷阱；
- 性能敏感场景可预处理：若业务允许，对潜在降序重复数据添加微小扰动（如 + random.random() * 1e-10）以规避 run 碎片化（需权衡精度）；
- Python 3.11+ 的 Powersort 改进：虽优化了归并策略与 minrun 计算，但run 检测逻辑未变，故该问题依然存在；
- 替代方案参考：对已知结构的数据（如双重复降序），可考虑手动分组 + reversed() + itertools.chain 等 O(n) 构造，而非依赖通用 sorted()。
总之，理解 Timsort 的 run 识别机制，是写出高性能 Python 排序代码的关键一环——算法的“智能”源于对数据模式的假设，而打破假设，代价往往远超预期。
