短段驱动的galloping归并

先倍增圈定，再二分收紧 ​

把长段当前未读位置记为start，末端记为end。定义单调谓词before(i)，表示该项应该排在当前短项x之前：原右长段用key<x，原左长段用key<=x。它在前面一串位置为真，之后为假。目标是第一处假；若全部为真，就返回end。

从start起按偏移0、1、3、7、15、…探测，即位置start+2ᵏ−1。每次看到真，便知道直到该位置都能批量输出，并把左界lo设到它后一位。首次看到假时，它给出右界；若探测位置已经超出end，就把end当作虚拟的假位置，不读取数组。

接着在[lo,hi)内二分。维持“lo之前已知真；hi是假位置或虚拟末端”的不变量：中点为真就令lo=mid+1，否则令hi=mid。lo=hi时恰是第一处假。整个搜索没有把键复制成切片，也没有从长段起点重新查找。

def gallop(a, start, end, key, upper, cost):
    def before(i):
        cost['comparisons'] += 1
        return a[i][0] <= key if upper else a[i][0] < key
    lo, step, probe = start, 1, start
    while probe < end:
        if not before(probe):
            break
        lo = probe + 1
        step *= 2
        probe = start + step - 1
    hi = min(probe, end)
    while lo < hi:
        mid = (lo + hi) // 2
        if before(mid):
            lo = mid + 1
        else:
            hi = mid
    return lo

upper只是选择严格或非严格谓词；搜索过程一致。cost记录真正调用键比较的次数，虚拟末端检查只比较下标。

外层归并为什么仍然正确 ​

始终保持：输出区已经是两段所消耗前缀的稳定合并，且没有未输出项应排在输出末项之前。短段内剩余项非降，因此下一短项x之前，长段应当先出的记录恰是before的真前缀。依次输出这个前缀，再输出x，就保持不变量；两种平局规则分别确保同键左记录先出。

长段边界只向前移动，从不退回。短段每轮至少消耗一项；若长段先耗尽，短段余下部分已经有序，可以直接接上。若短段先耗尽，长段余下部分同理。故算法终止，且不会漏掉、复制或交换同侧记录。

图的上下两种角色共用同一搜索器。绿色项先批量输出，蓝色项是当前短项，红色相等项是否留待稍后，由它来自原左还是原右决定。

一次搜索按跨过多少项付费 ​

设一次搜索从start到返回边界跨过d项。若d=0，只需检查第一项一次。若d>0，令h=⌈log₂(d+1)⌉。偏移2ʰ−1已经至少是d，故至多h+1次实际指数探测就会遇到假或越过末端。最后留下的待查区间长度至多2ʰ−1，二分至多h次键比较。因此统一有

即使第一次跳跃越过数组末端，这个界仍成立：末端不花键比较，只截短二分范围。长段远大于d时，也不会被迫支付log n；搜索从当前位置探测，只为当前短项实际跨过的前缀大小付费。[2，§2，B₁指数搜索]

等键放错一边，数值仍有序但记录已不稳定 ​

原左段是(2,L₀)、(2,L₁)、(4,L₂)，原右段是(2,R₀)。短段在右，处理x=2时必须先取长段里所有键≤2的项，得到L₀、L₁、R₀、L₂。若误用严格小于，就会得到R₀、L₀、L₁、L₂。两份输出的键都是2、2、2、4，只检查数值顺序看不出错误。

反过来，原左段只有(2,L₀)，原右段有(2,R₀)、(2,R₁)、(4,R₂)。短段在左，必须用严格小于，先输出L₀。这里若沿用上一例的≤，又会把两个右侧同键项插到L₀之前。

128项长段与3项短段 ​

长段键为0,…,127，短段键为31、63、95。短段在左时，第一轮要跳过长段0,…,30，共31项。指数探测的偏移为0、1、3、7、15、31，最后一项键31不满足严格小于；随后在[16,31)二分，返回边界31。当前短项先输出，长段的同键31暂时留下。

完整三轮共34次键比较，普通稳定双指针归并需要98次。交换左右角色后，第一次应跳过0,…,31，连同相等的31一起先出，完整galloping比较为36次，普通归并99次。两边总长度都是131：附件仍写入131条缓冲记录，再回写131条数组记录，并没有用34或36次操作完成全部输出。

若调用公开包装器验证这两段已经有序，还要额外127+2=129次键比较。这129次与核心34或36次分列；若实际调用方不提供有序性保证，就不能只报较小的自适应数。

跳跃不是每个输入都更省比较 ​

左段[2]，右段[0,1,3,4,5]。指数探测检查偏移0、1、3，再二分检查偏移2，共4次；普通归并只需把2依次与0、1、3比较，共3次。本页算法仍正确，但这个小例已经否定“只要使用指数搜索就逐实例胜过线性归并”。

实际库实现可以在连续多次从同侧取项后才进入galloping，并调节切换阈值。CPython文档描述了这种策略，以及短距离下指数搜索的额外开销。本页固定短段驱动，用于单独证明比较界；它没有实现min_gallop切换，也不代表某一库全部优化后的性能。[1，Galloping with a Broken Leg]

空段、全相等段、长段全部小于短项、短项全部小于长段，都由同一边界规则处理。比较器若不满足全序，例如把不可比较值随意当作相等，单调谓词和稳定有序合同都可能失效，不能由搜索循环补救。

把许多局部搜索合成总界 ​

设实际搜索q次，q≤m；第i次跳过dᵢ个长段项。边界不回退，所以Σdᵢ≤n。补上m−q个零值，并用⌈x⌉≤x+1，得到

对凹函数log应用Jensen不等式理路Jensen 不等式Jensen's inequality凸函数作用于平均值不超过函数值的相同加权平均。，等权平均后有Σᵢlog₂(dᵢ+1)≤m log₂(1+n/m)。于是

证明只用边界单调前移，不要求键互异，也不要求每轮跳过相同数量。m=0已提前退出；不能将0代入n/m后再谈极限。由于log₂(1+x)=O(x)，m≤n时比较工作也不超过O(n+m)，因此不会破坏整个归并的线性总工作界。

这个比较尺度为什么有意义 ​

只看互异键，两段内部次序已经固定，但它们可以有binom(n+m,m)种不同交错。一个只用二元键比较的决策树理路决策树模型Decision-tree model用查询节点、答案分支和输出叶刻画算法能够区分输入所需的信息深度。必须区分这些交错，因此某个输入至少要log₂ binom(n+m,m)次比较。又因为

最坏比较下界至少m log₂(1+n/m)。m≤n且m>0时log₂(1+n/m)≥1，所以本页上界与它只差常数因子。这是对所有合法交错的最坏界，不是声称任一具体输入都达到该下界。

比较、输出和随机访问分别收费 ​

附件使用完整输出缓冲：每条记录append一次，再按位置回写一次。因此归并的缓冲写入、数组写入各为n+m，辅助缓冲为O(n+m)，下标状态为O(1)。可选逐搜索日志另占O(m)；不记录日志时不保留那些条目。若只创建新输出而不回写原数组，可以省去回写步骤，但接口也相应改变。

这些界采用数组随机访问和字长足够保存下标的RAM，键比较成本独立计数。链表不能常数时间跳到第2ᵏ−1项；在链表上照搬探测位置公式而不记遍历代价，会错误宣称同样的时间优势。若每次键比较本身很贵，例如长字符串或远程比较，自适应比较数才尤其有用。

在Powersort理路Powersort自然归并排序Powersort · Power sort · Powersort自然归并用相邻自然段中点的二进制分歧决定归并次序，构造保持叶序的近最优归并树，并分别核算比较、搬移和调度成本。中，这个算法作为可替换的稳定双路工具。调度根据段长和位置确定，工具根据实际值交错决定比较数。两者组合的单元终结任务要求同时交出归并树与身份顺序，防止只凭较少比较就误判整个排序正确或更快。