归并排序

归并排序把数组分成两半，递归排好每一半，再反复取出两边最前面的较小值，将它们合并。时间复杂度为 O(n log n)，需要 O(n) 辅助空间；相等时先取左边，就能保持稳定性。

把两叠已经按姓名排好的试卷合在一起，比从头整理一堆乱序试卷容易：比较两叠最上面的姓名，取靠前的那张，重复直到取完。归并排序先把数组拆到每段只有一个元素，再通过合并构造越来越长的有序区间。

归并排序如何合并区间

sort(lo, hi) 处理一个连续区间。区间为空或只有一个元素时直接返回；否则用 mid = (lo + hi) // 2 分成左右两半，依次排好，再合并。

合并使用三个指针：i 指向左半段尚未取出的第一个元素，j 指向右半段的对应位置，k 指向辅助数组中的下一个空位。两边都有元素时，比较 arr[i] 与 arr[j]，把较小者写入 aux[k]，然后移动对应指针和 k。

比较条件是 arr[i] <= arr[j]。相等时先取左边，保证原来靠前的元素仍在前面。这就是归并排序保持稳定性的关键。某一边取完后，把另一边剩余的元素依次写入 aux，最后将 aux[lo..hi] 复制回 arr[lo..hi]。

归并排序逐步演示

默认输入为 [38, 12, 56, 7, 12, 41, 23]。把原下标 1 的 12 记作 12a，原下标 4 的 12 记作 12b，观察合并是否保留它们的顺序。

递归先处理左半段。[0..6] 在 mid = 3 处分成 [0..3] 和 [4..6]；[0..3] 再分成 [0..1] 和 [2..3]；[0..1] 最后拆成 [38] 与 [12a]。第一次合并比较 38 和 12a，先取右边的 12a，再取 38，得到 [12a, 38]。另一组 [56] 与 [7] 合成 [7, 56]。合并这两个有序区间，得到 [7, 12a, 38, 56]。

右半段 [12b, 41, 23] 在 mid = 5 处分开。先将 [12b] 与 [41] 合成 [12b, 41]，再与 [23] 合并：先取 12b，再取 23，最后补上 41，得到 [12b, 23, 41]。

最后合并 [7, 12a, 38, 56] 与 [12b, 23, 41]。先取 7，此时两边开头都是 12。因为使用 <=，先取左边的 12a，再取右边的 12b。接着依次取 23、38、41，最后补上 56。复制回原数组后，得到 [7, 12a, 12b, 23, 38, 41, 56]。两个 12 保持了原始顺序。

动画上方显示当前分治区间，下方展示本次合并。i 和 j 标出两个有序区间的开头，选中的元素先写入辅助行，再复制回主数组。最后一次合并中的相等比较，可以直接验证稳定性。

时间与空间复杂度

每层合并处理的元素总数为 n，每次拆半产生约 log n 层，因此总时间为 O(n log n)。本课采用自顶向下的递归实现，整次排序复用同一个 aux 数组，辅助数组占 O(n) 空间。

这种实现不会因为输入已经有序而跳过合并。它用额外内存换取稳定性和最坏时间保证；与快速排序相比，这是主要取舍。

边界情况

• 空数组或单元素数组：直接返回。
• 已经有序：仍然执行拆分和合并，时间复杂度为 O(n log n)，不会自动减少为线性时间。
• 逆序数组：合并时更常先取右半段，时间复杂度不变。
• 重复值：相等时先取左边，保留原始相对顺序。
• 奇数长度区间：按 (lo + hi) // 2 拆分，左半段比右半段多一个元素。

常见错误

• 把合并条件写成 <：结果仍按数值排序，但相等时先取右边，会破坏稳定性。只检查整数大小的测试可能发现不了。
• 忘记复制剩余元素：某一边取完，不代表另一边也取完。遗漏收尾循环会丢失元素。
• 把整个 aux 复制回去：只应复制 lo..hi。区间外可能还留着之前合并的数据。
• 每次合并都分配新缓冲区：结果可以正确，但会增加分配开销。复用一个长度为 n 的辅助数组即可。
• 两次递归后直接返回：左右两边各自有序，不代表整个区间有序，还必须执行合并。