外存排序 I/O 下界

信息计数图像 ​

排序必须区分 $N!$ 个输入排列理路排列Permutation有限集合到自身的双射，或其元素的有序排列。。某一时刻内存只有 $M$ 个记录；一次读入新块能选择哪些记录进入哪些内存位置，能新增的可区分布局受 $B$ 与已有 $M$ 限制。把每次 I/O 可扩大的排列状态数连乘，再要求覆盖 $N!$，取对数后得到上述下界。严谨证明用 I/O 图或 counting argument 处理块内容和磁盘位置，不能直接照搬二叉比较树的 $\log N!$。

为什么底数是 M/B ​

多路归并在内存中为约 $M/B$ 个 run 各留一块输入缓冲，再留输出缓冲；一轮扫描把 run 数缩小约 $M/B$ 倍，加上最初的 run 生成，总扫描轮数为 $O(1+{\log }_{M/B}(N/M))$，在 $N>M$ 时与 ${\log }_{M/B}(N/B)$ 同阶。下界说明在模型假设内，这种利用全部缓冲扇出的算法已达最优量级。

边界 ​

本页定理固定 $N>M\ge 2B$；若另取 $N\le M$，数据一次读入后可在内存免费排序，只需扫描 I/O。整数键允许 radix、压缩记录、批量编码或字操作时，indivisibility/比较模型改变；并行磁盘 $P>1$ 也改变每轮带宽。下界计传输次数，不模拟寻道、预取或 CPU 时间，不能跨模型宣称所有外排都受同一公式限制。

已知目的地址的置换与未知键序的排序 ​

Permuting 给每个原子记录一个目的位置，只需按这些位置重排。单磁盘下它的最坏最优 I/O 量级为

一条路线按目的位置外排；另一条路线逐项读取并写到指定位置，用 $O(N)$ 次 I/O。若 $B=1,M=2$ 而 $N$ 增长，已知地址的置换只需线性 I/O，未知键序的比较排序却需要 $\mathrm{\Theta }(N\log N)$。因此不可把两者的下界无条件写成同一个式子。Vitter 的 Theorem 5.3 与 §6.2 明确区分了这个小块参数区间。

比较模型中的完整计数 ​

先假设 $N$ 是 $B$ 的倍数，尾块一般情形只改变常数。为增强算法，可以在开始时免费告知每个输入块内部的键次序。原来的 $N!$ 种相对次序仍留下

种块间排列需要区分。

把一次读块及其后所有免费的内存比较看成一个多分支查询节点理路决策树模型Decision-tree model用查询节点、答案分支和输出叶刻画算法能够区分输入所需的信息深度。。内存中已有记录的相对次序可视为已知；读入块的内部次序也已知，因为它是原始已排序块，或此前曾同处内存、其内部次序已经确定的写出块。最多 $B$ 个新记录与最多 $M$ 个内存记录的未知关系，只是两条有序序列如何交错，分支数至多

读哪个地址以及写哪些记录，由此前比较结果决定，在比较模型中不会额外揭示键序。写块本身也不增加新比较信息。于是若最坏用了 $t$ 次 I/O，必须有

对数、Stirling 估计和 $N>M\ge 2B$ 给出

再结合读写全部记录的扫描下界，即得到定理。对均匀分布的这些块间次序，同样得到平均成本下界：若叶深度为 $d_1,\dots ,d_K$、分支上限为 $R$，沿树逐层分配质量给出 $\sum _i{R}^{-d_i}\le 1$；算术—几何平均不等式再给出 $R^{-K^{-1}\sum _i{d}_i}\le 1/K$。平均深度因此至少为 ${\log }_{R}K$。对总是正确的随机算法固定随机币后应用此式，再对随机币平均，就得到某个输入上的相同期望 I/O 下界。在原子置换模型中，目的位置本身可用于选择磁盘地址，不能把它当作仅由比较结果决定的选择；这正是上述更强比较论证的适用边界。

当 $N\le M$ 且 $N\ge 1$ 时，一次装入再写出仅需 $\mathrm{\Theta }(\lceil N/B\rceil )$ 次 I/O。整数分桶、记录压缩、多磁盘并行及输入已在缓存中，都会改变这里的操作或初态条件，应另作分析。

该下界解释了多路外归并的排序量级为何在原子比较模型中不可改进，并成为外存优先队列、缓存无关排序和批处理结构的基准成本。任何声称突破它的算法都必须指出改变的是整数键操作、记录可压缩性、磁盘并行度还是内存模型，而不能只比较公式表面。