8.7 外部排序、败者树·选择题讲评

外排核心指标是I/O。增加归并路数可减少趟数，败者树降低多路选择比较，置换选择可增长初始段。

手工推演与代码

归并路数越大不代表无成本，需更多缓冲并维护选择结构。

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

正确性与错解反馈

正确性来自每一趟扩大已确定区域且不破坏未处理数据。把内排时间公式直接套外排；败者树每次全树重建；虚段参与实际I/O。

迁移训练

多路归并中败者树的主要作用？答案把选最小头元素降到O(logk)比较。