外存排序

外归并排序理路归并排序Merge sort递归排序两半并线性合并的稳定比较排序算法。的关键不是减少比较，而是让每一趟都顺序搬完整块，并用内存同时供给尽可能多的输入 run。内存能容纳约 $M/B$ 个输入缓冲，因此一趟可把 run 数缩小同样倍数；这直接形成对数的底数，也解释了二路归并为何浪费外存带宽。

边界 ​

公式抽象了随机 I/O、CPU 比较与设备并行，不能直接预测 SSD 常数。Distribution sort 需要键分布/分桶条件。$B,M$ 以元素还是字节计须一致，tall-cache 假设只在使用它的算法中注明。

CPU 的 $O(N\log N)$ 不能机械换成同阶 I/O；顺序块传输才是外存算法核心。

下界按块能区分的排列数计数；若键宇宙允许 radix 或 distribution 技巧，纯比较 I/O 下界需要重新审视。稳定性也须在归并相等键时显式保留原先次序。

Run 生成与多路归并 ​

每次读入 $M$ 项在内存排序并写出一个 run，共 $\lceil N/M\rceil$ 个。归并时为每个输入 run 保留一块缓冲、为输出保留一块，故 fan-in 为 $\mathrm{\Theta }(M/B)$ 而非 $M$；最小堆选择各缓冲头，块耗尽再读下一块。

例如 $N=5\times {10}^8,M={10}^6,B={10}^3$，生成 500 个各有 ${10}^6$ 项的 run。选择 500 路归并，输入缓冲占 $5\times {10}^5$ 项，输出块和各路堆/游标仍有充足空间，因此一轮就能归并完成。二路归并需要 $\lceil {\log }_{2}500\rceil =9$ 轮，两者都另付最初的 run 生成成本。

排序公式的推导 ​

设初始 run 数为 $r_0=\lceil N/M\rceil$。选择 $f\ge 2$ 路后，归并轮数为 $\lceil {\log }_f{r}_0\rceil$，加上初始生成的一轮扫描，总成本为

当 $N\le M$ 时，$r_0=1$，没有外部归并轮。对 $N>M$，利用 $f=\mathrm{\Theta }(M/B)$ 和

便得到前述排序量级。常数内存比例及各轮最后不足一块的部分不会改变此界。

在不知道具体块大小 $B$ 与缓存容量 $M$、但采用理想缓存假设时，Funnel Sort理路Funnel Sortfunnel sort · 漏斗排序以递归多路合并器和分级缓冲，在不知道缓存参数时达到外存排序量级的块传输界。以递归漏斗归并实现 cache-oblivious 比较排序，并达到排序 I/O 界所要求的渐近扫描效率。它不是任意存储层上的无条件替代：证明依赖块传输、最优替换和 tall-cache 一类模型条件，工程实现还需处理写放大与并发 I/O。

实现与模型边界 ​

同键稳定归并要优先较早 run 中记录。Replacement selection 可生成平均更长 runs，却依输入分布；distribution sort 利用键结构，不受纯比较下界同样约束。SSD 并行、预取和 CPU 比较改变常数，但不会让随机单项访问自动等于块扫描。

四帧九页的逐趟账本与下游融合 ​

为把渐近式落实为精确页数，另取9页定长记录、4个数据帧，控制游标另计。初始run生成每次原位排序至多4页，再从已有帧写出，形成长度4、4、1页的三个run。读9写9，成本18。归并用三帧分别缓冲三个run，一帧输出；最小头项每次从其run移除，输出序列始终是已消耗项的有序排列。再读9写9，合计36次I/O，保留每一份重复记录。

再取13页、仍为4帧与三路归并：初始4、4、4、1页四个run，下一趟合成12页和1页两个run，再下一趟合成13页。若采用每趟完整读写、连未参与多路合并的单run也复制的明确调度，三趟共2×13×3=78次I/O。允许把单run原样保留可省其复制，但那是另一个需要逐文件记账的调度，不能把优化后的数字套进完整趟公式。

若消费者可以立即按该键做分组聚合，最终归并不必把9页有序文件写盘再读回：将归并输出直接交给消费者，外排阶段成本变为初始18加最后读9，即27，另计聚合输出。相对于“完整排序36再扫描9”，省去18次临时I/O。消费者只维护当前键及固定大小聚合状态，并能在原输出帧中形成摘要；若它还需更多同时驻留的数据帧，就必须重新分配，不能一边使用三路归并四帧，一边另借一帧。

排序归并连接理路排序归并连接与重复键组Sort-merge join · Merge join · Duplicate-key join groups先有序再按同键组作笛卡尔配对，给出四帧实现、重复组溢写退路和线性扫描成本的准确适用条件。也可尝试最后归并趟融合，但两侧各有多个run时，需要同时保留两侧输入缓冲、重复键组与输出。两次排序各自有四帧并不意味着融合连接仍只用四帧。DB-4选择先把两输入各物化成一个run，再按两游标、一重复组、一输出的四帧调度，避免隐藏额外缓冲。