归并排序与分治框架

归并排序是分治法最干净的例子：把数组一分为二，递归排好两半，再在线性时间内合并两个有序序列。

1. 分治的三步

对区间 $A[l..r]$ ：

Divide：取中点 $m=\lfloor(l+r)/2\rfloor$ ；
Conquer：递归排序 $A[l..m]$ 和 $A[m+1..r]$ ；
Combine：把两个有序区间合并成一个有序区间。

MergeSort(A, l, r):
    if l >= r: return
    m = floor((l + r) / 2)
    MergeSort(A, l, m)
    MergeSort(A, m + 1, r)
    Merge(A, l, m, r)

2. 合并为什么是线性的

设左右数组分别为 $L$ 和 $R$ ，用两个指针指向尚未取出的最小元素：

i = 1, j = 1
while i <= length(L) and j <= length(R):
    if L[i] <= R[j]:
        append L[i]; i += 1
    else:
        append R[j]; j += 1
append the remaining suffix

每个元素只被比较、复制常数次，所以合并长度为 $n$ 的两个区间需要 $\Theta(n)$ 时间。

有些伪代码会在两个临时数组末尾放 $+\infty$ 哨兵，以省掉“是否耗尽”的分支。真实程序若元素类型没有安全的无穷大值，显式判断边界更稳妥。

3. 正确性证明

3.1 Merge 的循环不变式

每轮合并前：

输出数组已经包含 $L$ 和 $R$ 中最小的若干元素，并按序排列；两个指针分别指向各自剩余部分的最小元素。

下一项必然是 $L[i]$ 和 $R[j]$ 中较小者。取走它后，不变式继续成立。某侧耗尽时，另一侧剩余部分本身有序，直接追加即可。

3.2 MergeSort 的归纳证明

长度 0 或 1 的数组天然有序；
假设所有更短数组都能被正确排序；
两个递归调用得到有序左右半区，正确的 Merge 再得到完整有序区间。

因此归并排序正确。

4. 时间复杂度

把 $n$ 个元素分成两个约 $n/2$ 的子问题，合并耗时 $\Theta(n)$ ：

T(n)=2T(n/2)+\Theta(n).

递归树第 $i$ 层有 $2^i$ 个规模 $n/2^i$ 的子问题，该层总代价仍为 $\Theta(n)$ 。树高 $\Theta(\log n)$ ，所以

T(n)=\Theta(n\log n).

最好、平均和最坏情况都是这个量级，因为无论输入原来是否有序，标准归并排序都会完成同样的递归与合并结构。

5. 空间、稳定性与适用场景

5.1 空间

数组版合并通常需要 $O(n)$ 辅助空间，递归栈深度 $O(\log n)$ 。链表合并可以通过改指针完成，额外空间更小。

5.2 稳定性

当 $L[i]=R[j]$ 时优先取左侧元素，归并排序就是稳定的：相等关键字的原相对顺序不变。若比较写成严格小于并优先取右侧，就会破坏稳定性。

5.3 外部排序

数据大到放不进内存时，可以先把若干块分别排好序写入磁盘，再做多路归并。归并按顺序读写，特别适合外部排序。

6. 小例子

排序 $[5,2,4,7,1,3,2,6]$ ：

[5,2,4,7]        [1,3,2,6]
[5,2] [4,7]      [1,3] [2,6]
[2,5] [4,7]      [1,3] [2,6]
[2,4,5,7]        [1,2,3,6]
[1,2,2,3,4,5,6,7]

注意两个值为 2 的元素来自不同半区。合并时先取左半区的 2，就能保持稳定。

7. 常见错误

区间采用闭区间还是半开区间前后不一致；
中点和递归边界导致长度为 2 时无限递归；
合并结束后忘记复制未耗尽的一侧；
把辅助数组写回原数组时下标偏移；
声称“分成两半所以是 $O(\log n)$ ”，忽略每层总共仍处理 $n$ 个元素。