Lecture 34：外部排序

外部排序的瓶颈通常是外存读写，而不是内存中的一次比较。基本路线是“生成初始归并段 → 多路归并”；优化则从两个方向入手：增大归并路数 $k$，或减少初始归并段数 $r$。

34.1 外部排序与归并过程

34.1.1 基本模型

定义：#外部排序 #初始归并段

描述：当待排序文件不能全部装入内存时，将外存数据分批读入内存、在内存中形成有序段并写回外存；这些有序段称为初始归并段。之后反复归并，直到只剩一个有序文件。

• 磁盘以块为单位读写；记录必须读入内存后才可比较、修改，处理后再成块写回外存。
• 外部排序的总开销可概括为：

$$ T_{\text{外排}}=T_{\text{外存读写}}+T_{\text{内部排序}}+T_{\text{内部归并}} $$

• 通常 $T_{\text{外存读写}}$ 占主导，因此优先减少 I/O，再降低内部归并的关键字比较次数。

图示：16 块文件先形成 8 个初始归并段，再经 3 趟二路归并得到最终有序文件。

34.1.2 二路归并与 I/O 计数

• 二路归并至少需要两个输入缓冲区和一个输出缓冲区，即 3 块内存缓冲区。
• 每次比较两个输入缓冲区的当前记录，将较小者送入输出缓冲区。输入缓冲区空时，从对应归并段读入下一块；输出缓冲区满时，整块写回外存。
• 某一归并段已耗尽后，另一归并段的剩余记录可直接依次输出，但仍要完成相应的块读写。

图示：输出缓冲区已有 $1,8,9$，两个输入缓冲区当前候选记录为 $26$ 与 $25$，下一条应输出 $25$。

• 若文件共有 $b$ 个磁盘块，每个完整阶段都读遍并写遍全文件，则该阶段约有 $2b$ 次块 I/O。
• 设初始归并段数量为 $r$，采用 $k$ 路平衡归并，则归并趟数为：

$$ s=\left\lceil\log_k r\right\rceil $$

• 若把“生成初始归并段”也按一次完整读写计入，概略 I/O 为：

$$ 2b(s+1) $$

• 原图示例中 $b=16$、$r=8$、$k=2$，因此生成初始段需 $2b=32$ 次 I/O，3 趟归并需 $3\times 2b=96$ 次，总计：

$$ 32+3\times 32=128 $$

• 必须按题目给定的“块数、初始段生成方式、是否计入初始段生成、每趟是否读写全文件”计算；上式是均匀平衡归并的常用模型，不能脱离条件硬套。

---

34.2 多路归并与败者树

34.2.1 多路归并的取舍

• 增大归并路数 $k$ 会使 $\lceil\log_k r\rceil$ 降低，从而减少读写全文件的归并趟数。
• $k$ 路归并至少需要 $k$ 个输入缓冲区和一个输出缓冲区；若内存总缓冲块数为 $m$，最直接的上界通常为 $k\le m-1$。
• 若每次直接顺序扫描 $k$ 个当前候选记录选最小者，最多需要 $k-1$ 次比较；$k$ 过大将增加内部归并时间。

图示：归并树的叶结点是初始归并段，树高对应归并趟数。减少树高可以减少整文件读写次数。

34.2.2 败者树

定义：#败者树

描述：败者树是一种锦标赛式选择树。叶结点对应各归并段的当前记录；普通内部结点保存该场比较的败者，胜者继续向上比较。总冠军通常保存在树顶的额外位置或单独槽位，而不是笼统地由普通内部根结点同时保存。

图示：绿色叶结点对应 8 个归并段的当前记录；灰色内部结点保存每轮败者；最上方蓝色位置保存最终胜者。

• 初次建立含 $k$ 个候选者的锦标赛需要 $k-1$ 次关键字比较，时间为 $O(k)$。
• 输出全局最小记录后，从其所属归并段补入下一条记录；若该段已空，则补入大于所有有效关键字的哨兵 $+\infty$。
• 只有从该叶到树顶的比赛结果可能变化，因此在平衡实现中最多重新比较：

$$ \left\lceil\log_2 k\right\rceil $$

图示：归并段 1 补入新记录后，只沿原冠军路径逐层与已保存的败者重新比较，无须重建整棵树。

• 若总共输出 $N$ 条记录，败者树辅助的内部选择总时间为 $O(N\log k)$；顺序扫描候选者则为 $O(Nk)$。
• 这里的 $k$ 是归并路数，不是初始归并段数 $r$；$r$ 用于计算归并趟数。
• 败者树只减少内部比较，不改变“每一归并趟仍需读写全文件”的基本 I/O 量。

WARNING · 原资料第 6 页的数值误写 原 PDF 称“1024 路败者树更新需比较 19 次”，但 $1024=2^{10}$，平衡败者树从叶到顶只有 10 层比赛，更新最多比较 10 次；19 不能由该路数推出。首次建树的比较次数仍为 $1024-1=1023$ 次，两者不可混淆。

NOTE · 教材补充：外部排序的稳定性边界 外部排序只有在初始归并段的生成过程稳定，并且多路归并遇到等键时以原输入先后作为最终判定，才能保证整体稳定。对按原文件连续分块生成的归并段，较早的段次序可表达这一先后；更一般的生成方式可携带原输入序号。败者树只改变候选记录的选择效率，其比较器也必须使用同一等键规则，否则等键记录仍可能换序。

---

34.3 置换—选择排序

34.3.1 目标与核心约束

定义：#置换选择排序

描述：利用容量为 $w$ 的内存工作区生成初始归并段。每次输出当前未冻结记录中的最小关键字并读入一条新记录；若新记录小于本归并段刚输出的关键字，则将它冻结到下一归并段。

• 普通分批内部排序时，一个完整初始归并段的长度通常不超过工作区容量 $w$。
• 置换选择生成的归并段可能长于 $w$，从而减少 $r$ 和后续归并趟数；在输入关键字独立、连续、随机等常见假设下，平均段长约为 $2w$，但这不是任意输入下的保证。
• “冻结”记录不能继续输出到当前段，因为它会破坏当前段的非递减顺序；它仍留在工作区，供下一段使用。
• 可用最小堆或败者树维护当前未冻结记录中的最小者。

34.3.2 算法步骤

1. 从输入文件 FI 读入至多 $w$ 条记录至工作区 WA。
2. 从当前未冻结记录中选最小者，记作 MINIMAX，输出到归并段文件 FO。
3. 若 FI 非空，读入下一条记录补入 WA。
4. 若新记录关键字不小于刚输出的 MINIMAX，它可参与当前归并段；若更小，则将它冻结。
5. 重复步骤 2～4，直到 WA 中不存在当前段可用的未冻结记录；写入归并段结束标志。
6. 解冻 WA 中的记录，开始下一归并段；当 FI 已空且 WA 也为空时结束。

• MINIMAX 是当前归并段最后输出的关键字，也是后续可输出记录的下界；相等关键字可以继续进入当前非递减归并段。
• 置换选择只负责生成初始归并段，不能替代后续多路归并。

34.3.3 数值过程：工作区容量 $w=3$

初始工作区为 $WA={4,6,9}$，其余输入依次为：

$$ 7,13,11,16,14,10,22,30,2,3,19,20,17,1,23,5,36,12,18,21,39 $$

• 归并段 1：依次输出 $4,6,7,9,11,13,14,16,22,30$。读入 $10,2,3$ 时，它们分别小于当时刚输出的下界，最终全部冻结。
• 解冻 $2,3,10$ 后生成归并段 2：依次输出 $2,3,10,17,19,20,23,36$；其中 $1,5,12$ 被留给下一段。
• 解冻后生成归并段 3：依次输出 $1,5,12,18,21,39$。

工作区只能容纳 3 条记录，但三个归并段的长度分别达到 10、8、6，体现了置换选择可突破固定分批长度的特点。

---

34.4 最佳归并树

定义：#最佳归并树 #多路Huffman树

描述：当初始归并段长度不等时，以各段长度为叶结点权值构造 $k$ 叉 Huffman 树，使带权路径长度最小；该树称为最佳归并树。

• 若某归并段有 $w_i$ 个块、在归并树中的深度为 $l_i$，它要在 $l_i$ 趟归并中各被读、写一次。所有归并阶段的块 I/O 为：

$$ 2\sum_i w_i l_i=2\operatorname{WPL} $$

• 上式不含最初生成归并段的 I/O；若题目要求总 I/O，还要另加初始段生成阶段。
• 构造方法：反复选择当前权值最小的 $k$ 个结点合并为新结点，再把新权值放回集合；所有非叶结点权值之和等于 WPL。
• 为使严格 $k$ 叉树满足叶结点数关系，需要补入权值为 0 的虚段。设原有 $r$ 个初始归并段，补入数量为：

$$ x=\Bigl((k-1)-(r-1)\bmod(k-1)\Bigr)\bmod(k-1) $$

• 等价条件是：

$$ r+x\equiv 1\pmod{k-1},\qquad 0\le x<k-1 $$

• 虚段必须在最初作为零权叶结点参与选择，不能随意补在树的高层；否则未必得到最小 WPL。
• 当各初始段等长且可以做完全平衡归并时，平衡归并树已经最优；长度不等时，最佳归并树可以减少总读写量。

题型：#外部排序I/O计算

第一部分：解题方法

1. 求初始归并段数 $r$；若使用置换选择，按模拟得到的实际段数和段长计算，不能直接用文件总量除以工作区容量。
2. 根据可用缓冲区确定归并路数 $k$，通常需要 $k$ 个输入缓冲区和 1 个输出缓冲区。
3. 等长平衡归并可用 $s=\lceil\log_k r\rceil$ 求趟数；不等长段要求最少 I/O 时，应构造最佳归并树并计算 $2\operatorname{WPL}$。
4. 构造 $k$ 叉最佳归并树前先计算零权虚段数 $x$，再反复合并最小的 $k$ 个权值。
5. 明确题目是否计入初始段生成，以及一次“读写”按 1 次还是“读 1 次、写 1 次”共 2 次计数。

相关知识

• 科目导航：数据结构导航
• 阅读顺序：上一篇：归并排序与基数排序 · 下一篇：排序算法总结
• 关联专题：排序代码

34.5 本节复盘

• 外部排序用初始归并段和多路归并处理超内存数据，核心代价是磁盘块 I/O。
• 多路归并通过增大 $k$ 降低归并趟数，但增加缓冲区和内部选择成本；败者树将每次重新选择降为 $O(\log k)$。
• 置换选择通过拉长初始归并段减少 $r$，与增大归并路数分别从两端减少 $\lceil\log_k r\rceil$。
• 初始归并段长度不等时，用补零后的 $k$ 叉 Huffman 树最小化 WPL；归并阶段块 I/O 为 $2\operatorname{WPL}$。
• 计算题必须先统一“块数、归并路数、是否计入初始段生成、读写计数口径”，再套用公式。