【引入】
在 外部排序 中讨论过，增大归并路数 $k$ 或减少初始归并段个数 $r$，都可以减少归并趟数 $S$，进而减少 I/O 次数，以提高外部排序速度
若总的记录个数为 $n$，每个归并段长度为 $l$，则归并段个数 $\left \lceil \frac{n}{l} \rceil \right.$，采用内部排序得到的各个初始归并段，除最后一个外，长度都相同，其依赖于内部排序时可用内存工作区的大小
因此，为产生更长的初始归并段，以减少初始归并段数 $r$，引入了置换-选择算法
【置换选择排序】
设待排序文件为 F1，初始归并段输出文件为 FO，内存工作区为 WA，FO 和 WA 的初始状态为空，WA 可容纳 $w$ 个记录
那么，置换选择排序的算法步骤如下：
1）从待排文件 FI 输入 $w$ 个文件到工作区 WA
2）从工作区 WA 选出关键字最小的记录，记为miniMax 记录
3）将 miniMax 记录输出到输出文件 FO
4）若待排文件 FI 不空，则从 FI 输入下一记录到工作区 WA 中
5）从工作区 WA 所有比 miniMax 记录大的关键字中选出最小关键字记录，作为新的 miniMax 记录
6）重复 3）~ 5），直到在工作区 WA 中选不出新的 miniMax 记录为止，由此得到一个初始归并段，并输出一个归并段的结束标志到输出文件 FO
7）重复 2）~ 6），直到工作区 WA 为空，由此得到全部初始归并段
需要注意的是，在工作区 WA 中选择 miniMax 记录的过程，需要用败者树来实现
以待排文件 FI 中的数据 $\{17,21,5,44,10,12,56,32,29\}$ 为例，设工作区 WA 容量为 $3$，排序过程如下：
输出文件 FO |
工作区 WA |
miniMax 记录 |
输入文件 FI |
|---|---|---|---|
| $-$ | $-$ | $-$ | $17,21,5,44,10,12,56,32,29$ |
| $-$ | $17,21,5$ | $5$ | $44,10,12,56,32,29$ |
| $5$ | $17,21,44$ | $17$ | $10,12,56,32,29$ |
| $5,17$ | $10,21,44$ | $21$ | $12,56,32,29$ |
| $5,17,21$ | $10,12,44$ | $44$ | $56,32,29$ |
| $5,17,21,44$ | $10,12,56$ | $56$ | $32,29$ |
| $5,17,21,44,56$ | $10,12,32$ | $-$ | $29$ |
| $5,17,21,44,56,EOF$ |
此时，在工作区 WA 中选不出新的 miniMax 记录，得到一个初始归并段 $\{5,17,21,44,56\}$，工作区 WA 非空，重新选择 miniMax 记录，以继续获得初始归并段
输出文件 FO |
工作区 WA |
miniMax 记录 |
输入文件 FI |
|---|---|---|---|
| $-$ | $10,12,32$ | $10$ | $29$ |
| $10$ | $29,12,32$ | $12$ | $-$ |
| $10,12$ | $29,32$ | $29$ | $-$ |
| $10,12,29$ | $32$ | $32$ | $-$ |
| $10,12,29,32$ | $-$ | $-$ | $-$ |
| $10,12,29,32,EOF$ | $-$ | $-$ | $-$ |
此时，得到另一个初始归并段 $\{10,12,29,32\}$，工作区 WA 为空，算法终止
得到全部的初始归并段 $\{5,17,21,44,56\}$、 $\{10,12,29,32\}$
【最佳归并树】
文件经过置换选择排序后，得到的是长度不等的初始归并段，为使 I/O 次数最小，那么就需要合理的组织长度不等的初始归并段的归并顺序
将霍夫曼树的思想推广到 $k$ 叉树的情形，在归并树中，让记录数最少的初始归并段先归并，记录数多的初始归并段最晚归并，即可建立总 I/O 次数最少的最佳归并树
若初始归并段不足以形成一棵严格 $k$ 叉树，需要添加长度为 $0$ 的虚段
设度为 $0$ 的结点有 $n_0$ 个，度为 $k$ 的结点有 $n_k$ 个，则对于严格 $k$ 叉树有 $n_0=(k-1)n_k+1$，由此可得：
若 $(n_0-1)\%(k-1)=0$，则说明这 $n_0$ 个叶结点(初始归并段)正好可以构成 $k$ 叉归并树，此时内结点有 $n_k$ 个
若 $(n_0-1)\%(k-1)=u\neq 0$，则说明这 $n_0$ 个叶结点中有 $u$ 个多余，不能包含在 $k$ 叉树中，为构造包含所有 $n_0$个初始归并段的 $k$ 叉归并树，应在原有 $n_k$ 个内结点的基础上再增加 $1$ 个内结点，代替一个叶结点的位置，被代替的叶结点再加上多出的 $u$ 个叶结点（$k-u-1 $个空归并段），即可建立归并树
如下图，用 $8$ 个归并段构造 $3$ 叉树，由于有：
说明了 $7$ 个归并段刚好构成一棵严格 $3$ 叉树，为此，将叶子 $5$ 变为一个内结点，再添加 $3-1-1=1$ 个空归并段，即可构成一棵严格 $k$ 叉树
