外部排序、败者树与多路归并

考点定位

本课深化 外部排序、败者树与多路归并。408作答必须同时给出数据结构表示、算法过程、不变量、复杂度和边界条件。

结构与取舍

数据不能全放内存时，先生成初始归并段，再多路归并。增加归并路数可减少趟数，但输入缓冲、比较结构和设备并行度限制实际路数。

算法推演

r个初始归并段做k路平衡归并，趟数为ceil(log_k r)。败者树把每次选最小记录的比较降到O(log k)；置换选择可生成平均更长的初始段。

把算法写成“初始化—循环条件—状态更新—终止输出”。若使用递归、队列、堆或并查集，要指出其中保存的状态及何时失效。

正确性不变量

每一归并趟后，归并段数量最多缩小为原来的ceil(r/k)。

初始化时不变量成立；一次迭代保持它；循环结束时它与终止条件共同推出答案。这是算法题证明的最短主线。

复杂度与边界

时间复杂度必须按输入规模和存储结构计算，不能只报结论。严格边界：外排总成本主要由磁盘I/O决定，不能只比较CPU次数。

随课应用

16个初始归并段进行4路平衡归并，需要多少趟归并？

先独立计算或编码，再完成单选与多选。代码题从标准输入读取并写到标准输出，不得硬编码样例；数值题需写出中间状态。