每天学一个算法--外部排序（External Sorting）

📘 教案 23：外部排序（External Sorting · 工程级）

一、问题模型（必须精确定义）

给定一个包含 (N) 条记录的数据集，单条记录大小为 ® 字节；主存（RAM）可用容量为 (M) 字节；磁盘以**块（block）**为单位读写，每块大小为 (B) 字节。

目标：对全部数据按某键排序。

约束：

[N⋅R≫M][ N \cdot R \gg M ][N⋅R≫M]

即：数据无法一次性装入内存。

二、评价指标：I/O 复杂度

外部排序的瓶颈不是 CPU，而是磁盘 I/O 次数。标准度量为：

[I/O cost=读块数+写块数][ \text{I/O cost} = \text{读块数} + \text{写块数} ][I/O cost=读块数+写块数]

我们以“扫描全数据一次”的 I/O 代价为基准：

[Θ!(NRB)][ \Theta!\left(\frac{N R}{B}\right) ][Θ!(BNR​)]

三、两阶段多路归并（TPMMS）

外部排序的标准算法是Two-Phase Multiway Merge Sort (TPMMS)：

Phase 1：生成初始有序段（runs）

• 每次读入至多 (M) 字节（约 (M/R) 条记录）
• 在内存中排序（任意内部排序算法）
• 写回磁盘形成一个有序段（run）

得到有序段数量：

[r≈⌈NRM⌉][ r \approx \left\lceil \frac{N R}{M} \right\rceil ][r≈⌈MNR​⌉]

Phase 2：多路归并（k-way merge）

• 同时打开 (k) 个有序段
• 为每个段分配一个输入缓冲区，为输出分配一个输出缓冲区
• 使用最小堆（优先队列）维护当前各段的最小元素
• 反复输出最小元素，直到完成

四、关键参数：归并路数 (k)

设每个缓冲区大小为 (B)，需要：

• (k) 个输入缓冲
• 1 个输出缓冲

内存约束：

[(k+1)⋅B≤M⇒k≤⌊MB⌋−1][ (k + 1) \cdot B \le M \Rightarrow k \le \left\lfloor \frac{M}{B} \right\rfloor - 1 ][(k+1)⋅B≤M⇒k≤⌊BM​⌋−1]

五、归并轮数（passes）

若一次不能归并完（即 (r > k)），需多轮归并。

归并轮数约为：

[⌈log⁡kr⌉][ \left\lceil \log_k r \right\rceil ][⌈logk​r⌉]

六、总 I/O 复杂度

• Phase 1：读一遍 + 写一遍
  [2⋅Θ!(NRB)][ 2 \cdot \Theta!\left(\frac{N R}{B}\right) ][2⋅Θ!(BNR​)]

• Phase 2：每一轮归并读+写一遍

总计：

[Θ!(NRB)⋅(1+⌈log⁡kr⌉)⋅2][ \Theta!\left(\frac{N R}{B}\right) \cdot \left(1 + \left\lceil \log_k r \right\rceil \right) \cdot 2 ][Θ!(BNR​)⋅(1+⌈logk​r⌉)⋅2]

简化表达（忽略常数）：

[O!(NBlog⁡MBNM)][ O!\left(\frac{N}{B} \log_{\frac{M}{B}} \frac{N}{M}\right) ][O!(BN​logBM​​MN​)]

这就是外部排序的经典 I/O 复杂度。

七、Phase 1 优化：替换选择（Replacement Selection）

目标：让初始有序段更长，减少 ®。

方法：

• 使用最小堆维护当前可输出元素
• 新读入元素若 (\ge) 上一次输出，则继续当前 run
• 否则标记为“下一 run”

结果：在随机输入下，平均 run 长度约为：

[≈2M][ \approx 2M ][≈2M]

于是：

[r≈NR2M][ r \approx \frac{N R}{2M} ][r≈2MNR​]

👉 直接减少一半的段数，从而减少归并轮数。

八、归并实现细节（可落地）

1. 缓冲区设计

• 每个输入 run 分配 1 个 block 缓冲
• 输出 1 个 block 缓冲
• I/O 采用顺序读写（避免随机 I/O）

2. 数据结构

• 最小堆大小为 (k)
• 每个堆元素记录：当前值 + 来源 run 的标识

3. 流程

1. 各 run 读入首块到输入缓冲

2. 将各缓冲的首元素入堆

3. 反复：

   • 弹出最小值写入输出缓冲
   • 从对应 run 的缓冲取下一个元素入堆
   • 若该缓冲耗尽，则读入该 run 的下一块

九、工程优化要点

1. 增大 (k)

[k↑⇒归并轮数↓][ k \uparrow \Rightarrow \text{归并轮数} \downarrow ][k↑⇒归并轮数↓]

但受限于 (M/B)。

2. 顺序 I/O

• 避免随机读写（性能数量级差异）
• 文件按 run 连续存储

3. 压缩 / 列式存储（场景相关）

减少 ®，从而减少 I/O 量。

4. 并行化

• 多磁盘并行读写

• MapReduce / Spark：

  • Map：生成局部有序段
  • Shuffle：按 key 分区
  • Reduce：分区内归并

十、与内存排序的本质差异

十一、适用场景

• TB / PB 级日志排序
• 数据仓库（ETL 排序阶段）
• 数据库 ORDER BY / GROUP BY
• 大规模去重（结合外部排序 + 归并去重）

十二、结论性表述

外部排序通过将数据划分为可内存处理的有序段，并以多路归并的方式逐步合并，在受限内存条件下以最小化 I/O 次数为目标完成全局排序，其性能由块大小、内存容量与归并路数共同决定。