8.5.1 归并排序

归并排序递归排两半，再用双指针线性合并。相等时先取左半可保持稳定；时间始终nlogn，辅助数组O(n)。

手工推演与代码

合并[1,4,7]与[2,4,6]依次取1,2,左4,右4,6,7。

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

正确性与错解反馈

正确性来自每一趟扩大已确定区域且不破坏未处理数据。某半耗尽后漏复制剩余；相等先取右破坏稳定；原地空间误报O(1)。

迁移训练

合并[2,5]与[1,3,6]，答案[1,2,3,5,6]。