⑴ 对题目所给关键字序列进行置换-选择排序：

初始FI：51，94，37，92，14，63，15，99，48，56，23，60，31，17，43，8，90，166，100；

WA和FO均为空。

第一趟：

从FI读4个记录到WA：51，94，37，92

从WA选择最小的值，记不MINIMAX，输出到FO：37

从FI读1个记录到WA：51，94，92，14

从WA选择最小，但不小于当前MINIMAX的值，输出到FO：37，51

重复上面两步操作，依次得：

WA：94，92，14，63

FO：37，51，63

WA：94，92，14，15

FO：37，51，63，92

WA：94，14，15，99

FO：37，51，63，92，94

WA：14，15， 99，48

FO：37，51，63，92，94，99

WA：14，15，48，56

此时已选不出新的MINIMAX，得第一个归并段：37，51，63，92，94，99

第二趟：

WA：14，15，48，56

FO：14

WA：15，48，56，23

FO：14，15

WA：48，56，23，60

FO：14，15，23

WA：48，56，60，31

FO：14，15，23，31

WA：48，56，60，17

FO：14，15，23，31，48

WA：56，60，17，43

FO：14，15，23，31，48，56

WA：60，17，43，8

FO：14，15，23，31，48，56，60

WA：17，43，8，90

FO：14，15，23，31，48，56，60，90

WA：17，43，8，166

FO：14，15，23，31，48，56，60，90，166

WA：17，43，8，100

此时已选不出新的MINIMAX，得第二个归并段：14，15，23，31，48，56，60，90，166

第三趟：

WA：17，43，8，100

FO：8

WA：17，43，100

FO：8，17

WA：43，8，100

FO：8，17，43

WA：100

FQ：8，17，43，100

最后分成三个归并段：

37，51，63，92，94，99

14，15，23，31，48，56，60，90，166

8，17，43，100

(2) 设输入序列为x₁,x₂,...,x_n，且所有关键字互不相同。

考虑最大值的情况：

显然，刚开始进入WA的m个关键字一定能被输出，如果后面每次进入WA的关键字都能被输出，只要该关键字恰巧大于刚刚输出的关键字即可。特殊地，取x₁<x₂<...<x_n，则所有的关键字都能被输出到第一个归并段，此时第一归并段的长度取最大值n。

再考虑最小值的情况：

同样，刚开始进入WA的m个关键字一定能被输出，如果后面每次进入WA的关键字都不能被输出，只要该关键字恰巧小于刚刚输出的关键字即可。特殊地，取x₁>x₂>...>x_n，则只有前m个关键字被输出到第一个归并段，此时第一归并段的长度取最小值m。

假设初始待排序文件为输入文件FI，初始归并段文件为输出文件FO，内存工作区为WA，FO和WA初始为空，设内存工作区WA的容量可容纳w个记录。则置换-选择排序的操作过程为：

① 从FI输入w个记录到缓冲区WA；

② 从WA中选出其中关键字取最小值的记录，记为MINIMAX记录；

③ 将MINIMAX记录输出到FO中去；

④ 若FI不空，则从FI输入下一个记录到WA中；

⑤ 从WA中所有比MINIMAX记录的关键字大的记录中选出最小关键字记录，作为新的MINIMAX记录；

⑥ 重复③~⑤，直到在WA中选不出新的MINIMAX为止，由此得到一个初始归并段，输出归并段结束标志到FO中；

⑦ 重复②~⑥，直到WA为空，由此得到全部初始归并段。