Timsort与powersort归并模式关联及栈容量计算原理问询

两者的核心设计目标完全一致：在run必须按原顺序相邻归并的约束下，构造总归并代价接近最优的字母归并树，最小化元素比较和移动的总次数。二者的差异只是最优性的近似实现路径不同，原始Timsort的长度不变量本质是Powersort规则的低开销工程近似：

• 归并优先级的判断逻辑本质一致：Powersort的power值本质是两个相邻run分隔点所在区间的深度，power值越高说明分隔点越靠近区间中点，两个run长度越接近，归并的单位代价越低，归并优先级越高。你观察到的“更高power对应更短run”是规律的表象：长度接近的两个短run归并，总代价远低于把短run和长run优先合并，这和原始Timsort“优先合并相邻短run”的长度判断逻辑完全对齐。区别只是Powersort通过二分计算分隔点位置得到精确的优先级，原始Timsort省掉了区间位置记录和power计算，直接用栈顶run的长度关系做硬判断，实现更简单，在早期硬件上缓存友好性更好。
• 不变量设计的目标本质一致：Powersort只维护B <= A的单不变量，本质是维护归并笛卡尔树的右链，保证所有高优先级的相邻run对都已经被合并，永远只需要处理栈顶两个run的归并。原始Timsort的两个不变量Y > X、Z > Y + X（X为栈顶最新run，Y、Z依次往栈底方向排列），是在没有精确优先级的前提下，强制栈内run长度从栈顶到栈底按黄金分割比例指数增长，避免出现“短run被夹在两个长run之间最后才合并，导致总归并路径长度飙升”的最坏情况。
• 归并选择的逻辑本质一致：Powersort因为有精确的power值排序，入栈新run时会把所有栈顶优先级低于当前分隔点的相邻对全部合并，所以永远只需要合并栈顶的Y和X。原始Timsort没有精确优先级，当出现X + Y >= Z的情况时，说明先合并Y和X得到的新run长度会超过Z，破坏栈的指数增长约束，这时候就选择合并Z和Y，本质是用长度规则模拟笛卡尔树的右链调整，保证归并树的总路径长度始终在最优值的小常数范围内。

实测下来原始Timsort的归并模式在绝大多数自然数据上的性能和Powersort差距在5%以内，只有在run长度分布极端不均匀的人工构造数据上，Powersort的近最优性才会体现出明显优势，这也是后续主流实现切换到Powersort的核心原因。

栈容量不需要动态扩容、不需要做越界检查的核心原因是：归并不变量强制栈内run长度从栈顶到栈底呈指数级增长，给定数组总长度的前提下，栈的最大深度存在严格的理论上界，预分配的栈长只要大于这个上界就永远不会溢出。

魔数的计算逻辑 #

Java版Timsort固定MIN_MERGE=32，即除了最后一个run之外，所有自然run的长度如果不足32，都会用二分插入排序补到至少32。结合原始Timsort的不变量要求：对栈内任意三个相邻run（从栈底到栈顶方向为Z、Y、X），必须满足Z > Y + X，栈顶往栈底方向的run最小长度构成类斐波那契序列：

• 栈顶第1个run（最新扫入的）最小长度32
• 栈顶第2个run最小长度32
• 栈顶第3个run最小长度 > 32+32 = 64，取65
• 栈顶第4个run最小长度 > 32+65 = 97，取98
• 后续每个run的最小长度都是前两个run最小长度之和加1，增长速度约为黄金比例φ≈1.618的指数级。

按这个序列累加不同栈深能容纳的最小总数组长度，再留1个位置的冗余，就得到了源码里的阈值和对应栈长：

• 数组长度<120时，理论最大栈深为4，分配5个槽位足够
• 数组长度<1542时，理论最大栈深为9，分配10个槽位足够
• 数组长度<119151时，理论最大栈深为18，分配19个槽位足够
• 数组长度超过119151时，哪怕是int类型支持的最大数组长度（2^31-1≈21亿），理论最大栈深也不超过39，分配40个槽位足够。

CPython固定用85的栈长，是因为它按MIN_MERGE=1的极端情况计算，85层斐波那契序列的累加和已经超过64位整数能表示的最大数组长度，不需要根据数组长度动态调整，实现更简单。

无越界防护的原因 #

• 逻辑上已经严格保证栈不会溢出：只要归并不变量的判断逻辑正确，栈的深度永远不会超过预分配值，加越界检查、动态扩容、强制合并的逻辑反而会给排序这个核心热点路径增加多余分支，拉低性能。
• 开发阶段已经用断言做了校验：OpenJDK源码的debug版本中存在栈深度的断言检查，正式发布版本关闭断言是因为逻辑正确性已经经过验证，不需要额外运行时开销。

注：2015年OpenJDK曾曝出Timsort栈越界bug，原因是最初的不变量判断逻辑存在疏漏，没有覆盖所有违反约束的场景，修复不变量判断逻辑后，栈溢出的可能性已经被完全消除。

内容的提问来源于stack exchange，提问作者z32a7ul