外存排序

I/O 上界 ​

在外存模型公理库外存 / I/O 模型External-memory model · I/O model · Aggarwal–Vitter model只计大小为 B 的数据块在容量为 M 的内存与外存之间传输次数的两层存储模型。中有 (N) 项、内存容纳 (M) 项、每块 (B) 项。扫描代价 (Scan(N)=\Theta(N/B))，比较排序最优量级

$$Sort(N)=\mathrm{\Theta }(\frac{N}{B}{\log }_{M/B}\frac{N}{B})$$

（$N>M$；能装入内存时只需扫描）。

外归并先生成 $M$ 大小有序段，再一次并 $\mathrm{\Theta }(M/B)$ 路：每路保留一个输入块并留输出块。二路归并会多做不必要的趟数，log 底数正来自并路数。

边界 ​

公式抽象了随机 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$ 倍，层数

$$\mathrm{\Theta }({\log }_{M/B}\frac{N}{B}),$$

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

实现与模型边界 ​

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

参考资料

• Aggarwal, Vitter, “The Input/Output Complexity of Sorting,” CACM, 1988.
• Jeffrey Vitter, Algorithms and Data Structures for External Memory, 2008.