8.7.1 外部排序

外部排序数据不能全放内存。先生成有序初始归并段，再多路归并。总I/O趟数主要由归并路数和初始段数决定。

手工推演与代码

8个初始段做2路需3趟归并；4路需ceil(log4 8)=2趟，但缓冲区和选择结构更复杂。

代码实现必须保持当前有序区、堆区或归并段的不变量，并对空数组、单元素、重复键和逆序输入测试。

正确性与错解反馈

正确性来自每一趟扩大已确定区域且不破坏未处理数据。只优化内存比较次数忽略磁盘读写；多路归并没有为每路留输入缓冲。

迁移训练

16段做4路需要几趟？答案2趟。