Python 内置 sorted() 使用 Timsort 算法，其性能高度依赖输入中“自然有序段”（runs）的数量；当列表由大量严格递减的双元素对构成时（如 [999999, 999999, 999998, 999998, ...]），Timsort 会错误地将每对视为独立的“严格降序 run”，导致运行数激增至百万级，从而大幅增加归并开销。
python 内置 `sorted()` 使用 timsort 算法，其性能高度依赖输入中“自然有序段”（runs）的数量；当列表由大量严格递减的双元素对构成时（如 `[999999, 999999, 999998, 999998, ...]`），timsort 会错误地将每对视为独立的“严格降序 run”，导致运行数激增至百万级，从而大幅增加归并开销。
Timsort 是 Python 的默认稳定排序算法，它并非单纯依赖比较，而是主动挖掘输入数据中的局部有序性——即识别并利用已存在的“runs”（自然升序或严格降序子序列）。这种设计使其在真实世界部分有序数据上表现极佳（接近线性时间），但也会在特定人工构造的模式下暴露性能边界。
关键在于 Timsort 对 descending run 的定义：必须是严格递减（>），而非非递增（>=）。这是为保障排序稳定性而做的关键取舍。例如，对 [2, 2, 1, 1] 这样的序列：
- 它不满足 a[0] > a[1]（因 2 > 2 为假），因此 [2, 2] 不能构成一个 descending run；
- 同理，[2, 1] 满足 2 > 1，但后续 1 与再下一个 1 又不满足严格递减；
- 最终，Timsort 将其切分为 n/2 个长度为 2 的 runs：[2,2], [1,1], [0,0], … —— 每个都因不满足严格递减而被当作“最小不可分单元”（需单独入栈），最终产生约 1,000,000 个 runs。
对比其他测试用例：
- a = [0,1,2,...] → 1 个长 ascending run
- b = [0,0,1,1,...] → 1 个 ascending run（0
- c = [...,2,1,0] → 1 个 descending run（...>2>1>0 严格成立）
- d = [...,1,1,0,0] → 1,000,000 个 runs（每个 [x,x] 都不满足 x > x，无法合并）
这直接导致 Timsort 的归并阶段需处理海量小片段，内存移动、栈操作和归并决策开销剧增——实测耗时从 ~35ms 跃升至 110ms，增幅超 3 倍。
以下代码可直观验证 run 数量差异（使用 list.__sizeof__() 或调试钩子不可行，但可通过修改 Timsort 源码或使用 timsort-debug 工具；此处提供逻辑等价的简化模拟）：
def count_timsort_runs(lst):
"""模拟 Timsort run 检测逻辑（仅用于教学理解）"""
if len(lst) <= 1:
return 1 if lst else 0
runs = 0
i = 0
while i < len(lst):
# 尝试扩展 ascending run: a[i] <= a[i+1] <= ...
if i + 1 < len(lst) and lst[i] <= lst[i + 1]:
j = i
while j + 1 < len(lst) and lst[j] <= lst[j + 1]:
j += 1
runs += 1
i = j + 1
# 尝试扩展 strict descending run: a[i] > a[i+1] > ...
elif i + 1 < len(lst) and lst[i] > lst[i + 1]:
j = i
while j + 1 < len(lst) and lst[j] > lst[j + 1]:
j += 1
runs += 1
i = j + 1
else:
# 单元素或相等对无法形成 run → 视为长度为 1 的 run（实际 Timsort 会 minrun 补齐，但数量级不变）
runs += 1
i += 1
return runs
# 验证
n = 1000
a = list(range(n)) # → 1 run
b = [i//2 for i in range(n)] # → 1 run (ascending with repeats)
c = a[::-1] # → 1 run (strictly descending)
d = b[::-1] # → ~n//2 = 500 runs
print(f"a: {count_timsort_runs(a)} runs") # 1
print(f"b: {count_timsort_runs(b)} runs") # 1
print(f"c: {count_timsort_runs(c)} runs") # 1
print(f"d: {count_timsort_runs(d)} runs") # 500 (≈ n/2)⚠️ 注意事项：
- 此行为不是 bug，而是 Timsort 为兼顾稳定性（stable sort）与常见场景性能所作的必要权衡；
- Python 3.11 引入的 Powersort 优化了归并策略，但未改变 run 检测规则，因此该现象依然存在；
- 若业务中频繁处理此类“重复值降序”数据（如倒排索引、分页缓存），建议预处理：先 sorted(lst, key=lambda x: (x, id(x))) 强制打破相等，或改用 heapq.merge 等更适合流式数据的方法；
- 性能调优时，应优先通过 timeit.repeat(..., repeat=5, number=1) 获取最小耗时，避免单次测量噪声。
总之，理解 Timsort 的 run 检测逻辑，是写出高效 Python 排序代码的关键一环——有序不等于“肉眼可见的顺序”，而是算法眼中符合其数学定义的结构。
