8.6 教材 8.6·综合题讲评

混合排序利用不同区间优势：快速排序递归到小区间改插入，并优先递归较小侧控制栈深。

手工推演与代码

分区得到大小2与n-3两段，先递归大小2，较大段用循环处理，可把额外栈限制在O(logn)。

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

正确性与错解反馈

正确性来自每一趟扩大已确定区域且不破坏未处理数据。两个分区都递归导致最坏栈O(n)；切换阈值过大；稳定性要求下仍用快排。

迁移训练

解释标准库排序为何常采用内省排序：快排快，深度过大转堆保最坏界，小段转插入。