自适应归并终结任务：交一份保留身份的排序账本
这条自然段与稳定归并路线的终点是一份可以重放的记录：不仅给出递增键，还保留每条原身份，说明何时合并哪些相邻区间，并把比较、搬移和调度计算分别记账。两项核心工具是Powersort与短段驱动galloping归并。
交付物与可运行附件
下载标准库执行器与完整执行结果。程序只向标准输出打印JSON，不写入工作目录，不依赖第三方包。普通与优化模式都用显式检查验证条件。
python algorithms-adaptive-merge-check.py
python -O algorithms-adaptive-merge-check.py交付记录应包含：原输入及原身份、每份自然段的区间和是否反转、边界power、push/pop/merge事件、最终树、叶深与体积、两种双路工具的比较数、初始复制/反转/缓冲/回写次数，以及下面三项迁移。只交一张已排序数组不足以核对稳定性和成本。
主输入：六份现成有序段
以下每行接在前一行后面，形成长度32的单一数组。身份是拼接后的原下标0,…,31，不是键值本身。
R0 = [8,14,27]
R1 = [1,3,9,11,17,19,29]
R2 = [6,25]
R3 = [0,2,4,7,10,13,20,24,31]
R4 = [5,12,18,30]
R5 = [15,16,21,22,23,26,28]自然扫描得到长度3、7、2、9、4、7，区间边界0、3、10、12、21、25、32，没有下降段要反转。扫描实际比较31次，恰好每一对相邻记录一次。
先核边界，再重放栈
| 相邻原段区间 | 中点分子，共同分母64 | 首次不同的位power |
|---|---|---|
| [0,3)，[3,10) | 3，13 | 3 |
| [3,10)，[10,12) | 13，22 | 2 |
| [10,12)，[12,21) | 22，33 | 1 |
| [12,21)，[21,25) | 33，46 | 3 |
| [21,25)，[25,32) | 46，57 | 2 |
这五次逐位循环一共执行3+2+1+3+2=11步。遇到power 2时先关闭左侧power 3子树；遇到power 1时再关闭左侧power 2子树。最大同时待定栈高为2。最后形成
(((R0,R1),R2),((R3,R4),R5))检查每个内部节点的两个孩子都是相邻原位置区间，父区间恰是二者并。叶节点仍按R0,…,R5排列；每个非根节点恰有一个父节点。附件的tree_certificate还核原段划分与每片叶的身份编号，不能用重复叶冒充另一段。
五次归并的实际账目
| 次序 | 相邻区间 | 体积 | galloping键比较 | 缓冲写入 | 数组回写 |
|---|---|---|---|---|---|
| 1 | [0,3)与[3,10) | 10 | 11 | 10 | 10 |
| 2 | [0,10)与[10,12) | 12 | 10 | 12 | 12 |
| 3 | [12,21)与[21,25) | 13 | 13 | 13 | 13 |
| 4 | [12,25)与[25,32) | 20 | 17 | 20 | 20 |
| 5 | [0,12)与[12,32) | 32 | 33 | 32 | 32 |
| 合计 | 整棵树 | 87 | 84 | 87 | 87 |
某一次galloping比较数可以超过该次体积，例如第一行11大于10；它保证的是自适应数量级，并不逐次受体积精确上界约束。换成稳定线性归并，调度和体积仍相同，五次归并比较总数为79。主例中galloping反而多比较5次，不能从算法名字推断实际更快。
初始带身份数组另外写32条记录；没有反转写。加上31次自然扫描，galloping的总键比较为115，线性版本为110。上述计数没有把边界下标比较、事件创建或JSON序列化混入“键比较”。
树深、熵和精确最优对照
叶深为3、3、2、3、3、2，加权得到87。nH约77.41281858，Powersort通用上界n(H+2)约141.41281858。附件用整数不等式验证，而不是用浮点近似决定通过与否：
另外用立方区间DP求这一小例的最优有序树。最优树可取((R0,(R1,R2)),(R3,(R4,R5)))，其内部体积为9、12、11、20、32，总计84。Powersort多付3，仍满足距离最优小于2n的保证；不应把87填写成精确最优值。
这个DP枚举所有区间及全部分隔，O(r³)时间、O(r²)存储；整数熵验证涉及大整数乘幂。二者只为小例提供对照，不属于O(1+n+nH)排序核心的一部分。
迁移一：同键身份与严格下降
改用键序列[5,4,4,3,2,2,1]，身份仍是原下标。不能把整份非增序列直接反转。合法自然段是[0,2)、[2,5)、[5,7)，三段都严格下降，分别反转共写6条记录。
最终完整记录序为
[(1,6),(2,4),(2,5),(3,3),(4,1),(4,2),(5,0)]注意两个2的身份4在5之前，两个4的身份1在2之前。该次扫描比较6次，归并比较8次，体积12，缓冲和数组回写各12。试着把下降条件从<改成<=，再检查原身份；仅核键递增会漏掉稳定性错误。
再单独合并短段[31,63,95]与长段[0,…,127]，检验相等键的方向。
| 短段位置 | 长段批量条件 | 每轮跨过数d | 每轮比较 | 归并总比较 | 线性归并比较 |
|---|---|---|---|---|---|
| 原左 | 键严格小于当前短项 | 31，32，32 | 10，12，12 | 34 | 98 |
| 原右 | 键小于等于当前短项 | 32，32，32 | 12，12，12 | 36 | 99 |
两次都输出131条记录，缓冲和回写各131。公开包装器另花129次比较验证输入已非降。把≤与<弄反时，数值仍可能正确，原身份顺序却会立刻暴露问题。
迁移二：相同段长，不同键交错
保持六段长度，改成以下互不交错的值域，每份内部仍升序：
R0 = [29,30,31]
R1 = [22,23,24,25,26,27,28]
R2 = [20,21]
R3 = [11,12,13,14,15,16,17,18,19]
R4 = [7,8,9,10]
R5 = [0,1,2,3,4,5,6]power仍为3、2、1、3、2，树深与体积仍是原来的87，但galloping归并比较变为25。解释时应指出：调度只看原位置和长度；比较器还看两段键值如何交错。因此同一棵树不能单独证明某种归并工具在该输入上比较更少。
迁移三：一个长段后面跟很多短段
段长改成1024，随后128份长度2的段。每段内部升序、相邻段的值域从大到小，确保自然扫描恰好识别这一轮廓。总长1280，原段数129。
Powersort得到体积3138，归并比较679，逐位power总步数1073，栈峰值8。若每来一段就并入左侧前缀，体积却是Σᵢ₌₁¹²⁸(1024+2i)=147584。用大段中任一条原记录参与多少次归并，解释两者差距，而不要只比较最终运行秒数。
空边界与最终验收
附件还执行空数组、单条记录、四条相等记录以及严格下降[9,8,7,6]。前三者没有归并；严格下降只需反转一段，同样M=0，但产生4次反转写与3次扫描比较。M为0并不代表整个算法零工作。
验收分开核五件事：输出每个原身份恰好一次；键非降且同键身份顺序不变；原段及power精确；树的相邻区间与叶深体积相符；比较与各类写入计数可由事件重放。record_trace=False关闭所有原段/树/事件日志，输出和计数仍相同；默认开启日志时的O(r)记录存储必须保留在空间账目中。
如果比较器成本、记录大小或机器字模型改变，应使用这份计数重新收费。尤其当输出必须实际物化时，较少键比较不会免除每次归并的线性记录写入。