“若叶子必须保留给定从左到右次序，最轻两项可能不相邻，普通Huffman合并就不满足这个额外约束。Powersort在稳定自然归并中处理这种有序叶树：段长承担叶权，体积等于加权叶深，算法得到距…”
形式陈述
已经有序的段应该在什么时刻合并
归并排序可以把两份已有序段稳定地合成一份。若原数组里已经存在很长的有序段，继续机械地拆到单个元素会丢掉这些信息。自然归并先找出这些段，再解决另一件事：每次选哪两个相邻段合并，才能少让大段反复参与搬移？
输入是长度n的随机访问记录数组，每条记录有键和不可丢失的原身份。键比较服从固定全序；稳定输出要求同键记录的先后次序与输入一致。附件把身份固定为原下标，键采用整数并拒绝布尔值。n=0输出空数组；n=1无需归并。
从左向右扫描。若下一个键小于当前键，就延长一个严格下降段并反转；否则延长一个非降段。严格下降在遇到相等键时必须停止，因为直接反转相等记录会破坏稳定性。每段至少非空，形成不相交半开区间
本页不通过插入排序强行延长短段。后续只合并相邻区间，段长Lᵢ=sᵢ₊₁−sᵢ。Powersort的输出是稳定排序结果；开启记录模式时还输出原段、每个边界的power、实际归并树及逐次成本。[1，§2、§3.2]
用原段中点定义power
把数组下标按n归一化到[0,1)。第i段的中点是cᵢ=(sᵢ+sᵢ₊₁)/(2n)。对于相邻两段，定义
把[0,1)连续等分为2、4、8份，Pᵢ就是两个中点首次落入不同小格的层数。小power表示较早的全局分隔，应当更靠近归并树根；大power表示更局部的分隔，应当较早完成。对恰在二进制边界上的中点，公式的floor约定决定它进入右侧格，不依赖浮点近似或二进制表示的两种写法。[1，Definition 3]
例如n=32，相邻段[0,3)、[3,10)的中点为3/64和13/64。乘2、4后两者的整数部分分别都是0；乘8后变成0与1，所以power为3。
直觉
一棵保持原次序的树
先暂时不动记录，把每段画成一片叶子。每合并两个相邻段，就为两棵相邻子树添一个父节点。叶子从左到右必须仍是R₀,…,Rᵣ₋₁。内部节点的权重等于它覆盖的记录数；把所有内部权重相加，称为归并体积M。
设第i片叶的深度为dᵢ，即到根的边数。该段每条记录在每个祖先处参与一次归并，因此
这让“别太早反复搬动大段”变得精确：重叶应尽可能浅，但不能随便交换叶子顺序。M是算法分析中的体积，不等于某次运行的键比较数。附件每次归并先写缓冲、再回写数组，两种记录写入各累计M。
power为什么足以确定整棵树
给所有中点写二进制小数，并采用尾随零的边界约定。共同的前缀表示它们仍在同一个小格里；下一位出现0和1时才分成左右两组。只保留真正发生分支的节点，删去只有一个孩子的中间层，就得到一棵满二叉树，其叶序与中点序相同。
任取连续的一组叶子。它们的最左、最右中点在某一位首次不同；此前整组中点都共享同一前缀。在该位，递增中点只能先是一串0，再是一串1，恰有一个相邻边界跨过分隔。这个边界的power是组内唯一最小值，其余边界都要等更深的位才分开。递归处理左右两组，得到唯一树。
因此可以直接复用笛卡尔树的“中序保持边界次序、根取最小优先级”构造。这里的power不是全局互异：不同子树可以都有power 3；刚才证明的是每个连续边界范围的最小值唯一，所以递归选根没有歧义。[1，§3.2；2，Appendix A]
从左向右关闭已经完整的子树
不必预先保存全树。用单调栈保存尚未找到右侧完整结果的左子树。每项是“已排好序的区间、其右边界power”，从栈底到栈顶power严格递增；另有一个当前段。
text
current = 第一份原段
依次读取下一份原段 next：
p = 按 current 与 next 的原段边界计算 power
当栈顶 power > p：
previous = 弹出栈顶区间
current = 稳定归并(previous, current)
将 (current, p) 压栈
current = next
原段已读完后：
持续弹栈，并稳定归并(previous, current)每轮开始的current是刚读取、尚未与左侧聚合的原段。先算p，再弹栈，这是代码顺序的一部分。弹栈后current的左端和长度会改变，却不能据此重新定义相邻原中点；p表示的仍是刚越过的原边界。
栈不变量还包括：栈内区间从左到右连续，接着就是current，它们恰好覆盖已处理前缀。遇到较小p时，所有更大power的栈顶节点都是它左侧已经读完的更深子树，先自底向上归并这些子树，再挂到p的左边。遇到较大p时，较浅节点的右子树还没读完，只能暂存。这个过程正是笛卡尔树的右侧路径更新，每个边界只进栈、出栈一次。
相等power不会在弹完更大者后成为栈顶：若左右两个相等最小power之间没有更小边界，就违反连续范围最小值唯一性。到达数组末端时，没有未读的右子树，再从栈顶归并到底即可。每次处理两个相邻有序区间，稳定性和最终有序性由双路归并归纳得到。
图中根对应power 1，它把前三段与后三段分开。相同的power 3位于不同子树，并没有在同一条根叶路径上重复。
逐位计算不需要浮点数
对相邻原段[l,m)、[m,r)，令a=l+m、b=m+r、D=2n。先把a、b乘2，比较它们是否至少为D。不同则当前位首次分歧；若相同且都至少D，就各减D，再求下一位。
循环入口的a、b都是未读二进制尾部的分子，落在[0,D)；乘2后的值小于4n，减D相当于删去已经相同的整数位。因此循环与floor定义完全一致，而且只用加倍、比较和减法。相邻中点相距(Lᵢ+Lᵢ₊₁)/(2n)≥1/n，所以到第⌈log₂n⌉位，它们不可能仍在同一个宽度不超过1/n的半开格内。n≥2时每个power至多⌈log₂n⌉，严格递增栈也至多这么高。[3，The Merge Pattern中的powerloop说明]
例子与边界
六段的手算轨迹
取段长(3,7,2,9,4,7)，累计边界为0、3、10、12、21、25、32。五个power依次是3、2、1、3、2。表中“入栈结果”只列power；区间归并在同一行给出。
| 新边界power | 先完成的归并 | 入栈结果 |
|---|---|---|
| 3 | 无 | 3 |
| 2 | [0,3)与[3,10) | 2 |
| 1 | [0,10)与[10,12) | 1 |
| 3 | 无 | 1，3 |
| 2 | [12,21)与[21,25) | 1，2 |
| 输入结束 | [12,25)与[25,32)，再合并[0,12)与[12,32) | 空 |
五个归并体积为10、12、13、20、32，总计87。叶深是(3,3,2,3,3,2)，另一种计法给3×3+7×3+2×2+9×3+4×3+7×2=87。长度的二进制熵约2.41915，因此nH≈77.41282，而n(H+2)≈141.41282，实际体积确实夹在两者之间。
“近最优”不等于“每组长度都最优”。同一组长度的最优有序二叉树体积是84；更小的反例(2,2,3,5)中，Powersort给24，最优给23。附件用小规模区间动态规划独立算这个基准：单叶成本为0，区间[i,j)选择分隔k，成本是两子区间最优值加本区间总长度。枚举所有k需要O(r³)时间、O(r²)空间，不属于Powersort主算法。
为什么不能反转非增段
带身份输入为(5,0)、(4,1)、(4,2)、(3,3)、(2,4)、(2,5)、(1,6)。它整体非增，却含两对相等键。若整体反转，身份2会排在身份1之前，身份5也会排在身份4之前。
规定严格下降后，扫描得到[0,2)、[2,5)、[5,7)三段；分别反转，再稳定归并，最终同键身份仍是4的1、2以及2的4、5。全相等数组则识别成一份非降段，完全不用归并。所有键互异的全下降数组可整段反转一次，体积M=0，但扫描和反转仍花线性工作。
为何不总是从左到右合并
若第一段长1024，后面有128段、每段长2，从左到右把新段并入巨大前缀，会支付1026+1028+⋯+1280=147584的体积。附件同一长度轮廓的Powersort体积为3138。长段不应在每个短段到来时都搬一遍。
长度轮廓只确定调度，无法确定比较数。终点把六段内部键换成互不交错的值域，仍是相同power和体积87；采用同一galloping工具时，归并比较却从84变成25。记录移动和键比较必须分开报告。
推论与应用
用中点深度证明接近最佳体积
对n>0，令pᵢ=Lᵢ/n。段长分布的二进制熵为H=Σᵢpᵢlog₂(1/pᵢ)。它看的是记录分布到各原段的比例；不是不同键的出现频率。只有一段时p₀=1、H=0、M=0。
固定第i段，取ℓᵢ=⌈log₂(1/pᵢ)⌉+1。包含该段中点的半开二进制格，宽度至多pᵢ/2；格内任一点到中点的距离小于等于pᵢ/2，所以这个格包含在该段原位置区间内，不可能含另一段中点。第ℓᵢ层以前就已把它与其他中点区分。压缩只有一个孩子的层只会缩短路径，故dᵢ≤ℓᵢ<log₂(1/pᵢ)+2。加权后得到
另一方面，任一只做二路归并的满树满足Kraft等式Σᵢ2⁻ᵈⁱ=1：根的质量1在每次分支时对半分，最后全落在叶子上。单叶树也成立，其深度为0。对凹函数log使用Jensen不等式，有
因此任何有序归并树的体积至少nH，Powersort的体积距离最佳值小于2n。这里的下界针对归并体积，不声称每次输入都必须进行nH次键比较；已经知道两段值域分离时，比较可以少得多。
把调度计算也记入运行时间
每个边界入栈、出栈各一次，但逐位计算power的成本不是自动O(1)。本页实现保守计为O((r−1)log n)个小整数操作。它仍能被O(n+nH)吸收：固定正整数段长的总和n和段数r，把两份大于1的长度逐单位往较大者集中，会增大ΣLᵢlog₂Lᵢ，因为x log x的离散增量递增。极端是(n−r+1,1,…,1)，从而
稳定线性归并每次花O(区间长度)工作；也可替换为短段驱动galloping归并，在值交错较少时降低比较数，同时显式写出整个归并结果的工作仍然线性。于是本页两种工具的核心总时间都是O(1+n+nH)。读入和类型校验、原身份复制、自然段扫描与反转均为O(1+n)，空输入出口仍花常数成本。
这个时间口径把键比较和O(log n)位下标操作各视为常数。若键是最长b位整数，键比较最坏需O(b)位工作；若按逐位模型实现下标加倍、比较、寻址，则不能继续把字操作免费。可先保留实际键比较次数C与小整数操作数，再按采用的机器模型收费。附件的精确大整数熵验证与立方最优树对照属于额外诊断，不能算进上述主算法界。
待定段栈占O(log n)项，当前归并缓冲最坏O(n)记录；返回带身份数组也占O(n)。默认教学记录模式另存r份原段、2r−1个树节点及O(r)条事件。设置record_trace=False即可去掉这些日志，排序结果与成本计数相同；不能把开启日志后的全部辅助空间说成O(log n)。
从一份排序结果回查调度证据
单元终结任务同时交最终身份序、原段边界、power、归并树、体积、比较数和写次数。按树的每个内部节点检查两孩子区间相邻且覆盖父区间，再把叶长乘深度，即可独立复算调度成本。最终键有序只说明排序成功，并不能替代稳定性、树结构或成本核对。
参考资料
- J. Ian Munro、Sebastian Wild，Nearly-Optimal Mergesorts: Fast, Practical Sorting Methods That Optimally Adapt to Existing Runs，ESA 2018，§§2.2–2.3、3.2，Definition 3、Lemma 4、Theorem 5、Algorithm 2，印刷63:6–63:10。作者PDF
- 同文2018-05-10扩展稿，Appendix A、A.1，PDF第15页，给出跳过空二分层及路径power单调性；本文另用有序中点的首分歧位展开证明。扩展稿
- CPython 3.13，Objects/listsort.txt，The Merge Pattern中Powersort及逐位power计算说明。固定版本只作工程接口参照；本文未加入其minrun或完整库级优化。源码文档