外存排序 I/O 下界

信息计数图像 ​

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

为什么底数是 M/B ​

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

边界 ​

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

Permuting 与 sorting ​

下界常先证明 permuting：把记录重排到任意指定顺序需要多少 I/O，再用排序产生的键次序编码排列。若记录可以拆成比原子更小片段或压缩许多键进一字，状态计数改变。反之，带 payload 的数据库记录排序通常正符合原子/indivisibility 假设。

$\mathrm{Sort}(N)$ 的 max 项正是在统一表达这个边界。当 $M/B$ 很大时，对数项可能低于 $1$，但每轮仍需读写 $\mathrm{\Theta }(N/B)$ 块；不能只看归并层数缩短而漏掉扫描输入的成本。

一个 I/O 能产生多少新排列 ​

内部内存一次容纳 $M/B$ 个块。读入一个新块后，算法可把其中 $B$ 个记录与内存中至多 $M$ 个记录重排，再选择 $B$ 个写出；单次 I/O 可区分的组合数量受大约 $(\genfrac{}{}{0ex}{}{M+B}{B})$ 控制。把所需区分的 $N!$ 个输入排列与每次 I/O 的分支能力比较，并同时保留输入扫描下界，得到

的 comparison-based 排序下界。

当 $N\le M$，数据一次装入内存，式子应退化到扫描输入输出的 $\mathrm{\Theta }(N/B)$，不能机械保留负数或小于 1 的对数。允许整数分桶、压缩键、多个独立磁盘或并行 I/O 时，决策能力改变，必须重新声明模型而非继续引用此下界。

下界衡量块传输，不计算内存内部比较次数。一个算法可以达到最优 I/O 却做更多 CPU 工作；外排序实践还要同时报告顺序读写、寻道和归并缓冲配置。

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