| 项目 | 值 |
|---|---|
| 主题 | 外部排序 |
| 核心概念 | 数据太大无法全装入内存时，用归并排序（对磁盘顺序访问最友好） |
| 时间复杂度 | $O(k)$、$O(\log_k m)$（趟数） |
| 难度 | ⭐⭐⭐⭐ |
当数据量太大，无法全部装入内存时，需要外部排序。外部排序主要使用归并排序，因为归并排序对磁盘的顺序访问特性最友好。
1. 生成初始归并段（run）：
- 每次将能装入内存的数据排序后写回磁盘
- 生成若干个有序的归并段
2. 多路归并：
- 将 k 个归并段进行 k 路归并
- 每次从 k 个段中取最小的元素输出
- 直到所有段归并为一个设初始归并段数为 $m$，归并路数为 $k$：
$$ \text{归并趟数} = \lceil \log_k m \rceil $$减少趟数的方法：
用于生成更长的初始归并段：
1. 从磁盘读入尽可能多的记录到内存
2. 选出最小值输出（属于当前归并段）
3. 从磁盘读入下一个记录
4. 若新记录 ≥ 刚输出的记录，属于当前段；否则属于下一段
5. 重复，直到当前段结束，开始新段平均可生成长度为内存大小 2 倍的归并段。
类似哈夫曼树，构造带权路径长度最小的归并策略：
k 路归并时，每次选出最小值需要比较 $k-1$ 次。使用败者树可以减少到 $\lceil \log_2 k \rceil$ 次。
败者树：完全二叉树
- 叶节点：k 个归并段的当前最小值
- 内节点：记录"败者"（较大值）
- 根节点：记录"胜者"（最小值）
选最小值后，只需沿着胜者路径更新，比较次数 = 树的高度| 考点 | 说明 |
|---|---|
| 归并趟数计算 | 给定段数和路数，求趟数 |
| 置换选择排序 | 手算生成初始归并段 |
| 最佳归并树 | 构造哈夫曼树，求读写次数 |
| 败者树 | 理解败者树的工作原理 |
| 补虚段 | k 路归并时如何补虚段 |