TimSort在部分有序数据下远快于手写快排，因其主动识别升序/降序run并跳过冗余比较，而快排易退化为O(n²)；它对天然run直接保留，短run用插入排序扩展，归并时满足x>y+z等条件并启用gallop模式，所有优化均在C层实现。
为什么部分有序数据下 list.sort() 比手写快排快得多
因为 list.sort() 底层是 TimSort，它不假设数据完全随机，而是主动扫描、识别已有的升序/降序片段（叫 run），并跳过大量冗余比较。而快排默认把每个子数组都当全新乱序处理，一遇到近乎有序的数据，就容易退化成接近 O(n²)。
常见错误现象：自己写的递归快排在处理「几乎已排好序的列表」或「含大量重复元素的列表」时，耗时暴涨，甚至触发 RecursionError；但 sorted() 依然稳定在 O(n) 到 O(n log n) 之间。
- TimSort 在发现长度 ≥32 的天然
run时，直接保留，不重排 - 对短
run（ - 快排若选错 pivot（如总选首/尾），在升序输入中每次只减少一个元素，递归深度达
n级
minrun 是什么，为什么取值在 32–64 之间
minrun 是 TimSort 划分初始 run 时的最小长度阈值，不是固定值，而是根据数组总长动态计算的——目标是让最终 run 数量接近 2 的幂，便于后续归并阶段高效配对。
例如数组长 1000，minrun 可能算出来是 32；长 5000 时可能变成 64。硬编码成 32 或 64 都会破坏这个平衡，导致归并栈频繁触发强制合并逻辑，拖慢性能。
- 太小（如设为 8）→
run过多 → 归并栈压力大，合并次数激增 - 太大（如设为 128）→
run过少，且很多短run被强行拉长，浪费插入排序开销 - Python CPython 源码里实际用的是
compute_minrun(n)函数，核心逻辑是“补足最低位的 1”
gallop 模式怎么减少归并时的比较次数
归并两个已排序 run 时，TimSort 不像朴素归并那样逐个比对，而是先用指数搜索（gallop）快速定位「某段连续元素全小于另一 run 的当前头元素」，然后整块复制过去。
这在现实数据中特别有效：比如合并 [1,2,3,...,50] 和 [100,101,102,...]，gallop 一步就能确认前 50 个数都该先输出，省掉 49 次比较。
- gallop 不是始终启用：只有当连续 7 次比较结果相同时才切入，避免小数组上得不偿失
- 一旦 gallop 失败（比如找到边界后又回退），立刻退回线性比较
- Java 的
Arrays.sort()同样实现了 gallop，但 Python 的触发阈值和回退策略更激进些
稳定性和自适应性不是白来的代价
TimSort 的稳定性（相等元素相对位置不变）和自适应性（对有序数据敏感）都依赖额外状态维护：需要记录每个 run 的起止、长度、是否翻转过；归并栈要实时检查 x > y + z 条件；每次 gallop 都要保存搜索路径……这些逻辑全在 C 层实现，Python 层不可见。
这意味着：你无法靠改几个参数就“加速 TimSort”，它的优化是整体性的；想绕过它用纯 Python 实现类似效果，大概率更慢——不仅因为解释器开销，更因为丢失了底层内存布局感知和分支预测配合。
真正容易被忽略的一点：TimSort 对「部分逆序」同样高效，但它会把降序 run 先原地翻转成升序再参与归并，这个翻转是 O(k) 时间但 O(1) 额外空间，很多人误以为它必须额外分配内存来存副本。
Python免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 Python 的核心概念和高级技巧！
