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

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

下文先建立 run 与合并代价的模型，再用一个交互区单步对比两种合并树；随后拆解 Timsort 的栈不变式（以及它曾导致的栈溢出），与 Powersort 的虚拟完全二叉树，最后补几处工程细节。

1 · run：把「已经有序」当作起点

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

实现里还会设一个 minrun 阈值（通常 32~64，由 n 动态定）：太短的天然 run 用二分插入排序 (binary insertion sort) 就地扩到 minrun 长度。这样合并阶段面对的 run 数量有上界，小规模段也走 cache 友好的插入排序而非递归归并。本页的交互聚焦合并阶段，故直接给定若干现成 run。

2 · 合并顺序决定总代价

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

这与 Huffman 编码 的最优合并、最优 BST 的有序建树是同一族问题：让长 run 尽量少参与几层合并。理论最优可用 $O(n^2)$ 区间 DP 求得，但排序要的是线性附加开销下的近似最优——这正是下面两种策略各自的答案。

3 · Timsort：一套栈不变式（和那个栈溢出 bug）

Timsort 边扫描边把 run 压入一个栈，并维持栈中相邻 run 长度的不变式，违反就立即合并。经典形式针对栈顶三个长度 A、B、C（C 在最顶）要求 A > B + C 且 B > C：这让栈中长度大致按指数衰减、相邻段规模相近（合并才均衡），栈深也被压在 $O(\log n)$。

2015 年有人证明：原始的三条规则其实不足以保证不变式对栈中更深的部分成立，构造特定的 run 长度序列能让栈越积越高、冲破预分配的容量上限而栈溢出（Java、Android、Python 的实现都中招）。修法是补上对栈顶第四个元素的检查（$S[n-4] \le S[n-3] + S[n-2]$ 也触发合并），即上面代码里的第二个条件。这段历史说明：这套基于长度比较的规则正确性难以一眼看穿，需要形式化证明才放心。

4 · Powersort：用虚拟完全二叉树定序

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

维护一个栈，每个 run 记着它左边界的 power。新 run 到来时算出新边界 power p，把栈顶所有 power 比 p 更大（更深、更该先合并）的 run 依次合并掉，再压入新 run。因为完全二叉树里相邻边界的 power 互不相同、且 power 上限就是树高 $\lceil \log _2 n\rceil$,栈深天然有上界（n 再大也不过 64 档）,无需 Timsort 那种需要证明的长度规则，且生成的合并树可证明是近似最优的（WPL 与最优只差一个常数项）。

5 · 几处工程细节