数据结构
2023-42
对含有 n (n>0) 个记录的文件进行外部排序，采用置换-选择排序生成初始归并段时需要使用一个工作区，工作区中能保存 m 个记录。请回答下列问题。
1）若文件中含有 19 个记录，其关键字依次是 51, 94, 37, 92, 14, 63, 15, 99, 48, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100，则当 m = 4 时，可生成几个初始归并段？各是什么？
2）对任意的 m (n >> m > 0)，生成的第一个初始归并段的长度最大值和最小值分别是多少？
答案
【答案】
(1) 可生成3个初始归并段，分别为：
- 归并段1：37, 51, 63, 92, 94, 99
- 归并段2：14, 15, 23, 31, 48, 56, 60, 90, 166
- 归并段3：8, 17, 43, 100
(2) 第一个初始归并段的长度最大值为 n，最小值为 m。