外部排序的总时间主要取决于：
因此优化方向有两个：
生成更长的初始归并段，从而减少归并段数量。普通方法：内存能装 $m$ 个元素，每个归并段长度为 $m$；置换选择排序：归并段平均长度为 $2m$。
内存大小为 4，输入序列：12, 25, 38, 10, 45, 5, 15, 30, 50, 3, 20, 60
| 步骤 | 输出 | 内存（最小堆） | 读入 | 判断 |
|---|---|---|---|---|
| 1 | 10 | [12, 25, 38] | 45 | $45 \geq 10$，加入 |
| 2 | 12 | [25, 38, 45] | 5 | $5 < 12$，冻结 |
| 3 | 25 | [38, 45, (5)] | 15 | $15 < 25$，冻结 |
| 4 | 38 | [45, (5), (15)] | 30 | $30 < 38$，冻结 |
| 5 | 45 | [(5), (15), (30)] | 50 | $50 \geq 45$，加入 |
| 6 | 50 | [(5), (15), (30)] | 3 | $3 < 50$，冻结 |
此时所有元素都被冻结，第 1 段结束：10, 12, 25, 38, 45, 50（长度 6，比内存大小 4 更长！）。第二段解冻 [5,15,30,3] 继续，得到 3, 5, 15, 20, 30, 60。共 2 个归并段（普通方法需 $12/4=3$ 个）。
当各归并段长度不同时，如何安排归并顺序使总 I/O 次数最少。
最佳归并树是一棵哈夫曼树，以各归并段的长度为权值构造。总 I/O 次数为：
$$ \text{I/O} = 2 \times \sum (\text{叶子权值} \times \text{路径长度}) $$
（乘 2 是因为每次归并都要读一次、写一次。）
5 个归并段，长度分别为 2, 3, 5, 7, 11：
$$ \text{I/O} = 2(2\!\times\!4 + 3\!\times\!4 + 5\!\times\!3 + 7\!\times\!2 + 11\!\times\!1) = 2\times 60 = 120 $$
设初始归并段数为 $m$，做 $k$ 路归并，则归并趟数：
$$ \text{趟数} = \lceil \log_k m\rceil $$
减少归并趟数的方法：
| 主题 | 结论 |
|---|---|
| 置换选择排序平均段长 | $\approx 2m$（输入随机时） |
| 归并段数 | $\approx n/(2m)$，比普通方法 $n/m$ 减少一半 |
| 最佳归并树本质 | 哈夫曼树，权值 = 归并段长度 |
| 补虚段条件 | $(m-1)\bmod(k-1)\neq 0$ 时需补 |
| 优化方法 | 作用 | 效果 |
|---|---|---|
| 置换选择排序 | 减少归并段数 | 平均段长从 $m$ 增至 $2m$ |
| 最佳归并树 | 减少 I/O 次数 | 按哈夫曼树归并，I/O 最少 |
| 增加路数 $k$ | 减少归并趟数 | 趟数 $= \lceil\log_k m\rceil$ |
（暂无关联知识点）