外存排序

外归并排序公理库归并排序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={10}^9,M={10}^6,B={10}^3$，初始约 1000 runs，一轮最多并约 1000 路，理想情况下单轮即可归并。二路归并却需约 10 轮，每轮读写全数据，I/O 高一个数量级。

排序公式的推导 ​

每层读写 $\mathrm{\Theta }(N/B)$ 块，run 数每层缩小 $M/B$ 倍，层数

乘积得到 Sort$(N)$。若 $N\le M$，数据一次装入，公式应截断为 $O(N/B)$，不能出现负对数。

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

实现与模型边界 ​

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