python 内置 sorted() 使用 timsort 算法，其性能高度依赖输入数据中“自然有序段”（runs）的数量；当降序序列中存在相邻相等元素时，timsort 无法将其识别为单个降序 run，导致将本应合并的长段切分为大量短 run，显著降低性能。
python 内置 sorted() 使用 timsort 算法，其性能高度依赖输入数据中“自然有序段”（runs）的数量；当降序序列中存在相邻相等元素时，timsort 无法将其识别为单个降序 run，导致将本应合并的长段切分为大量短 run，显著降低性能。
Timsort 是 Python 的默认稳定排序算法，它并非简单地执行归并或插入排序，而是自适应地利用输入中已存在的局部有序性。其核心优化在于：扫描数组，识别出尽可能长的“单调 run”，再将这些 run 作为基础单元进行归并。一个 run 被定义为满足以下任一条件的最大连续子序列：
- 升序 run：a[i]
- 降序 run：a[i] > a[i+1] > a[i+2] > ...（必须严格递减，不允许相等）
关键点在于：降序 run 的判定是严格的。这是为了保障排序的稳定性（stable sort）——即相等元素的原始相对顺序必须保留。若允许 >=，则 Timsort 在原地反转该 run 时，会打乱相等元素的位置（例如 [2, 2, 1] 反转为 [1, 2, 2]，两个 2 的顺序被颠倒），破坏稳定性。
我们来分析问题中的四组数据：
n = 2_000_000 a = [i // 1 for i in range(n)] # [0,1,2,...,1999999] → 单个升序 run b = [i // 2 for i in range(n)] # [0,0,1,1,2,2,...] → 单个升序 run（含重复） c = a[::-1] # [1999999,...,1,0] → 单个严格降序 run（无重复，满足 > 条件） d = b[::-1] # [999999,...,2,2,1,1,0,0] → 每对相等数构成“断点”
- a、b、c 均被识别为 1 个 run，后续归并开销极小；
- d 中，由于相邻相等（如 ...,2,2,...），不满足 > 条件，因此每个 x,x 对都会强制中断当前降序 run。实际上，d 被切分为约 1,000,000 个 run（每个 run 长度为 2，形如 [x, x]），而 Timsort 需要为每个 run 分配元数据、维护 run 栈，并执行大量细粒度归并操作，导致时间复杂度退化，实测耗时飙升至 3 倍以上。
可通过 array.array 或 list.__sizeof__() 辅助验证 run 数量，但更直观的是借助 timsort 的调试逻辑（如 CPython 源码中的 find_run 函数）。值得注意的是：即使在 Python 3.11 引入 Powersort（Timsort 的增强变体），其 run 检测规则保持不变，因此该性能现象依然存在。
✅ 最佳实践与规避建议：
- 若需频繁对含重复元素的近似降序数据排序，可预先 reversed() 后 sorted(..., reverse=True)，或使用 sorted(lst, key=lambda x: -x)（避免触发降序 run 判定）；
- 对性能敏感场景，可用 numpy.sort()（基于 introsort）替代，其对重复降序数据无此敏感性；
- 永远不要假设“看起来有序”的数据就一定触发 Timsort 最优路径——run 的定义是算法层面的精确规则，而非人类直觉。
简言之：Timsort 的优雅源于其对真实数据局部结构的敏锐捕捉，而这份敏锐，恰恰由“严格降序”这一看似苛刻的设计所守护。理解 run 的生成逻辑，是掌握 Python 排序性能调优的第一把钥匙。
