8.7 外部排序、败者树·综合题讲评

设计外排需联合计算初始段数、归并路数、趟数与段长权重；不等长段优先用最佳归并树。

手工推演与代码

段长2,3,7,9的二路方案合并代价38，若先7+9会让长段重复参与，代价更大。

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

正确性与错解反馈

正确性来自每一趟扩大已确定区域且不破坏未处理数据。只算最终写出一次；忽略每趟读写；最佳归并树漏补虚段。

迁移训练

说明增加内存如何减少I/O：能生成更长初始段、提高归并路数，从而减少归并趟数。