Timsort · Powersort

自适应归并排序 · run 的合并顺序

现实里待排序的数据极少是纯随机的——日志按时间近乎递增、追加写入只打乱了末尾、拼接的两段各自有序。quicksort 平均 $O(n \log n)$ ，却既不稳定、也无法利用这种天然有序性：无论输入多整齐，它都从头比一遍。自适应归并排序换一条路：先把序列切成已经有序的连续段 run，再像归并排序那样把这些 run 两两合并。难点不在「怎么合并」，而在合并的顺序——它直接决定总搬移量。Timsort 与它的 Powersort 变体区别只在这一处，run 识别、minrun、galloping、合并缓冲在 CPython 3.11 里原封不动。

1 · 天然 run 的识别

扫描数组，把极大的单调段切出来：连续不降的一段直接是一个 run；遇到严格递减的一段，原地反转即得升序 run（用严格 $>$ 判定递减才能保证稳定，相等元素不跨越反转）。一趟线性扫描后，数组就成了若干升序 run 的拼接。完全随机的输入退化成平均长度约 2 的 run（长度 $n$ 的随机排列，极大升段数的期望是 $(n+1)/2$ ）；基本有序的输入只有寥寥几个长 run，这是自适应排序省下功夫的地方。

实现里还会设一个 minrun 阈值（ $n \ge 64$ 时落在 32–64，由 $n$ 动态定； $n < 64$ 时 minrun 取 $n$ ，整段直接二分插入排序、不进合并阶段）：太短的天然 run 用二分插入排序就地扩到 minrun 长度。这样合并阶段面对的 run 数量有上界，小规模段也走 cache 友好的插入排序而非递归归并。

2 · 合并顺序与总代价

归并两个长度为 $a$ 、 $b$ 的有序段，最多要把这 $a+b$ 个元素都挪一遍，故单次合并代价记作 $a+b$ 。把全部 run 合成一个的总代价，等于每个 run 的长度乘以它被卷入合并的次数之和，也就是合并树的带权外部路径长度 (WPL)。于是问题变成：在保持 run 左右次序的前提下（相邻才能合并），怎样安排合并树让 WPL 最小？

注 · $a+b$ 是上界而非实测搬移量。CPython 的 merge_at 先用 gallop 定位 $b$ 的首元素在 $a$ 中的位置，之前的元素完全不搬；本页的代价模型取的是不带这层优化的口径，两棵合并树因此可比。

这与 Huffman 最优合并、最优 BST 的有序建树是同一族问题：让长 run 尽量少参与几层合并。理论最优可用区间 DP 求得，朴素写法是 $O(m^3)$ （ $m$ 为 run 数），加 Knuth 四边形优化到 $O(m^2)$ ；这个问题就是最优字母树，Hu–Tucker 与 Garsia–Wachs 可在 $O(m \log m)$ 内精确求解。但排序要的是线性附加开销下的近似最优。

图 2-1 · Timsort 与 Powersort 合并树的并排对照。可切换样本，读数给出各自的总搬移量——长短交替一例实测 55 对 47，等长五段是 65 对 60，基本有序与阶梯 run 两例两者相同。

注 · 长短交替一例的差距全部来自一个 run 的深度。实测叶深度 Timsort 是 3、3、3、3、1，Powersort 是 2、2、3、3、2：省下的 8 全来自第一个长 run 从深度 3 升到 2（ $8 \times 1$ ），第二个长 run 仍在深度 3，末尾的短 run 反而沉了一层。四个样本里 Powersort 的代价都等于区间 DP 算出的最优值。

3 · Timsort 的栈不变式

Timsort 边扫描边把 run 压入一个栈，并维持栈中相邻 run 长度的不变式，违反就立即合并。经典形式针对栈顶三个长度 $A$ 、 $B$ 、 $C$ （ $C$ 在最顶）要求 $A > B + C$ 且 $B > C$ 。这两条让栈内长度至少按 Fibonacci 速度拉开，从而只在长度可比时才触发合并，栈深也被压在 $O(\log n)$ 。

图 3-1 · merge_collapse 的三个分支：两条不变式各自被违反时，分别选择哪一次合并。

2015 年有人证明 [3]：原始的两条不变式只看栈顶三段，不足以保证它对栈中更深的部分成立，构造特定的 run 长度序列能让栈越积越高、冲破为 run 栈预分配的槽位数而越界 [1]（Java 里表现为 ArrayIndexOutOfBoundsException）。修法有两条路：Java 当年是加大栈数组，CPython 则补上对栈顶第四段的检查—— $S[n-4] \le S[n-3] + S[n-2]$ 也触发合并（图 3-1 里的第二个条件）。这段历史说明，基于长度比较的规则正确性难以一眼看穿，需要形式化证明才放心。

4 · Powersort 的 node power 定序

Powersort 换了视角：想象一棵覆盖整个数组下标区间 $[0, n)$ 的虚拟二分树 (bisection tree)，根代表整段、每往下一层把区间二等分。两个相邻 run 之间的边界落在这棵树的某条裂缝上，它的 node power 是两个 run 的中点在 $[0,1)$ 里第一个不同的二进制位的位置，也就是这条边界在虚拟树中的深度。power 越大表示边界越深、这两段应该越早合并。

图 4-1 · 边界的 node power 即它在虚拟二分树中的深度：两个 run 中点在二进制下第一个不同位的位置。

维护一个栈，每个 run 记着它左边界的 power。新 run 到来时算出新边界的 power $p$ ，把栈顶所有 power 比 $p$ 更大的 run 依次合并掉，再压入新 run。因为相邻边界的 power 互不相同、且 power 有上界，栈深天然有界，不需要 Timsort 那种要另行证明的长度规则。

注 · 上界比论文给的更紧一档。Munro–Wild 给的是 $\lfloor \lg n \rfloor + 1$ ，而对 $n = 2 \dots 120$ 穷举全部 $(s_1, n_1, n_2)$ ，最大 power 恒等于 $\lceil \log_2 n \rceil$ ，无一例外。栈里还要额外容纳栈底那项（其左边界 power 为 0），所以槽位数按 $\lceil \log_2 n \rceil + 1$ 预留才稳妥。

近最优性的度量是 run 长度分布的熵 $\mathcal{H}$ ：Powersort 的合并代价不超过 $n\mathcal{H} + 2n$ ，而任何合并树都不低于 $n\mathcal{H}$ [2]，故与最优只差一个 $O(n)$ 的加性项，平均到每个元素是常数次多余搬移。这不是「差一个常数因子」——枚举 $n \le 16$ 的全部 run 长度组合， $(\text{pow} - \text{OPT})/n$ 最大是 0.375（ $n = 16$ 、run 长度 1,2,1,1,6,1,1,2,1，53 对 47），恒为线性量级。

注 · Powersort 也不保证在每个输入上都比 Timsort 省。枚举 $n \le 18$ 的全部 262125 组 run 长度，Timsort 严格更优的占 32108 组（12.2%）。最小的反例是 1,1,1,1,2,1（ $n = 7$ ）：Timsort 18、Powersort 19，而最优是 18；差距最大的是 1,2,1,1,7,1,1,4（ $n = 18$ ），Timsort 48（正是最优）对 Powersort 56。Powersort 的价值不在逐例更省，而在总代价稳定接近最优、栈容量上界不必另证。CPython 自 3.11 起把 list.sort() 的合并定序换成了 Powersort。

警示 · nodePower 里的 a *= 2 不能改写成 a <<= 1。JS 的位运算把操作数截到 32 位， $n \ge 2^{31}$ 时会溢出成负数，两个分支都进不去而死循环。core/powersort.test.ts 有专门的回归，但这类错误只会以「整份测试卡住」的形式报警，不会给出失败断言。

5 · 合并阶段的工程手法

手法	作用
galloping（飞奔）	同一侧连赢 `MIN_GALLOP`（值为 7）次后切入 galloping：先按 1、3、7、15… 指数跳跃框定它能连胜多少个，再在框内二分，把 $O(k)$ 次比较压到 $O(\log k)$ 。`MIN_GALLOP` 会随成效自适应升降。
二分插入扩 run	天然 run 短于 minrun 时，用二分插入排序把后续元素并进来，凑到 minrun 长度；小段走插入排序比递归归并更 cache 友好。
反转递减段	严格递减的一段原地反转即成升序 run；用严格 $>$ 而非 $\ge$ 判定，保证相等元素不被反转，稳定性不受破坏。
合并缓冲	合并时只需把较短的一段复制到临时缓冲，再就地归并回去，额外空间为两段中较小者而非 $n$ 。

6 · 参考文献

de Gouw, S., Rot, J., de Boer, F. S., Bubel, R., & Hähnle, R. (2015). OpenJDK's java.utils.Collection.sort() is broken: The good, the bad and the worst case. In Computer Aided Verification (CAV 2015), LNCS 9206, 273–289.
Munro, J. I., & Wild, S. (2018). Nearly-optimal mergesorts: Fast, practical sorting methods that optimally adapt to existing runs. In 26th Annual European Symposium on Algorithms (ESA 2018), LIPIcs 112, 63:1–63:16.
Auger, N., Jugé, V., Nicaud, C., & Pivoteau, C. (2018). On the worst-case complexity of TimSort. In ESA 2018, LIPIcs 112, 4:1–4:13.