1.2 归并排序

上一篇的插入排序是 $O(n^2)$，这一篇的归并排序（Merge Sort）直接把它压到 $O(n\log n)$。它也是我们第一次正式接触分治——这门课后面会反复出现的设计思想。所以这一篇不只是学一个排序，更是理解"分治"这套范式的起点。

1.核心想法：先分，再合

归并排序的想法朴素得漂亮。给你一堆乱序的数，排序很难；但如果这堆数已经分成两半、每半各自排好了序，那把它们合成一个有序数组就特别容易——这就是"归并"。

于是策略就出来了：把大问题切成两半，递归地排序每一半，最后归并。 切到什么时候为止？切到只剩一个元素，一个元素天生有序，这就是递归的基底。

MERGE-SORT(A, p, r)        // 排序 A[p..r]
    if p < r:
        q = ⌊(p + r) / 2⌋   // 找中点
        MERGE-SORT(A, p, q) // 排左半
        MERGE-SORT(A, q+1, r) // 排右半
        MERGE(A, p, q, r)   // 合并两半

整个算法的精髓全在 MERGE 这一步。我们重点讲它。

2.归并：两个有序序列合成一个

设 $A[p..q]$ 和 $A[q+1..r]$ 都各自有序了。怎么把它们合成一个有序的 $A[p..r]$？用两根指针，从两半的头上各指一个，每次挑较小的那个拿走：

MERGE(A, p, q, r)
    n1 = q - p + 1          // 左半长度
    n2 = r - q              // 右半长度
    let L[1..n1+1], R[1..n2+1]  // 各多留一个哨兵位
    for i = 1 to n1: L[i] = A[p+i-1]
    for j = 1 to n2: R[j] = A[q+j]
    L[n1+1] = ∞             // 哨兵：∞ 保证比谁都大
    R[n2+1] = ∞
    i = 1, j = 1
    for k = p to r:         // 逐个填回 A[p..r]
        if L[i] <= R[j]:
            A[k] = L[i]; i = i + 1
        else:
            A[k] = R[j]; j = j + 1

末尾那个 $\infty$ 哨兵是个小技巧：当某一边拿空了，另一边剩下的元素都比 $\infty$ 小，会自然地被依次挑走，不用单独写"某一边空了"的分支判断，代码干净。

举个具体例子。两半分别是 [2, 5, 8] 和 [1, 4, 7]：

L=[2,5,8,∞]  R=[1,4,7,∞]
比较 2 vs 1 → 拿 1 → 结果 [1]
比较 2 vs 4 → 拿 2 → 结果 [1,2]
比较 5 vs 4 → 拿 4 → 结果 [1,2,4]
比较 5 vs 7 → 拿 5 → 结果 [1,2,4,5]
比较 8 vs 7 → 拿 7 → 结果 [1,2,4,5,7]
比较 8 vs ∞ → 拿 8 → 结果 [1,2,4,5,7,8]

你看，整个归并只扫了一遍，每个元素被看了一次。

3.复杂度分析：$O(n\log n)$ 怎么来的

归并排序最漂亮的地方在它的复杂度，我们来认真数一遍。

先看 MERGE 这一步。填 $A[p..r]$ 一共 $r-p+1=n$ 个位置，每个位置做一次比较、一次赋值，所以归并的代价是 $\Theta(n)$（正比于要合并的元素数 $n$）。

再看整体的递归。设 $T(n)$ 是排序 $n$ 个元素的总代价。算法把它对半切成两个 $n/2$ 的子问题，各花 $T(n/2)$，再花 $\Theta(n)$ 归并：

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

这是一个递归关系。怎么解？最直观的是画递归树（4.1 节会专门讲，这里先看直觉）：

            n              ← 第0层，代价 n
          /   \
        n/2   n/2          ← 第1层，代价 n/2 + n/2 = n
       / \    / \
     n/4 n/4 n/4 n/4       ← 第2层，代价 4×(n/4) = n
        ...                   每层代价都是 n
     1 1 1 1 ... 1          ← 第 log₂n 层，n 个叶子

关键观察：每一层归并的总代价都是 $n$（不管切到第几层，这一层所有归并加起来处理的元素总数还是 $n$）。一共切了多少层？每切一次规模减半，从 $n$ 切到 $1$ 要切 $\log_2 n$ 次，所以有 $\log_2 n$ 层。

于是总代价 = 每层代价 $\times$ 层数 = $n \cdot \log_2 n = \Theta(n\log n)$。

这就是 $O(n\log n)$ 的来历。注意它比插入排序的 $O(n^2)$ 快了一大截：$n=10000$ 时，$n^2=10^8$，而 $n\log n\approx 1.3\times 10^5$，差了近千倍。这就是分治的力量——把一个 $O(n^2)$ 的问题拆成两半递归，居然能省到 $O(n\log n)$。 第二卷你会看到这套"切两半"的招数能用在多少不同的问题上。

4.和插入排序比，归并排序好在哪、差在哪

	插入排序	归并排序
时间复杂度	$O(n^2)$（最坏/平均）	$O(n\log n)$（最坏也是这个，稳定）
最好情况	$O(n)$（近乎有序时飞快）	$O(n\log n)$（无论如何都走完整递归）
空间	$O(1)$，原地	$O(n)$，要额外数组做归并
稳定性	稳定	稳定

看出门道了没？没有哪个算法在所有维度上都赢。 归并排序在时间上完胜，但它不原地——每次归并都要开额外数组，空间 $O(n)$，在内存敏感的场景这就是硬伤。而且它不管输入长什么样都要老老实实跑完 $\log n$ 层递归，所以"近乎有序"这种插入排序能 $O(n)$ 捡便宜的好牌，归并排序反而捡不到。

工程选型从来不是"选复杂度最低的"，而是在时间、空间、稳定性、对输入的敏感度之间权衡。 这是你从这一篇要带走的核心意识。

5.练习

Q1. 对数组 [5, 2, 8, 1, 9, 3]，写出归并排序的递归切分过程和最终归并顺序。

先切 [5,2,8] 和 [1,9,3]；再切 [5] [2,8] 和 [1] [9,3]；[2,8] 归并成 [2,8]，[9,3] 归并成 [3,9]；[5] 和 [2,8] 归并成 [2,5,8]，[1] 和 [3,9] 归并成 [1,3,9]；最后 [2,5,8] 和 [1,3,9] 归并成 [1,2,3,5,8,9]。

Q2. 用递归树论证 $T(n)=2T(n/2)+\Theta(n)$ 的解是 $\Theta(n\log n)$。

每层归并的总代价都是 $\Theta(n)$（这一层所有子问题处理的元素总数加起来等于 $n$）。规模每次减半，从 $n$ 到 $1$ 共 $\log_2 n$ 层。总代价 = $\Theta(n)\times \log_2 n=\Theta(n\log n)$。树高 $O(\log n)$、每层 $O(n)$，相乘即得。（4.1 节会更系统地讲递归树。）

Q3.（思考题） 既然归并排序比插入排序快，为什么实际工程里很少把它作为通用排序的首选？

因为它需要 $O(n)$ 额外空间（不原地），而且常数和递归开销都不小。工业级排序更爱用快速排序（原地、平均 $O(n\log n)$，下一篇卷二的 2.1 讲），再在小段切回插入排序——综合了原地、快、常数小这几个优点。归并排序的用武之地在于它稳定且最坏也是 $O(n\log n)$，所以在"要求稳定排序"或"最坏情况不能太差"的场景（比如外部排序、链表排序）里仍然是首选。

6.小结

归并排序是分治思想的教科书级范例：把问题对半切开、递归解决、再线性归并。它把排序压到 $O(n\log n)$，代价是要 $O(n)$ 额外空间。更重要的，它递归关系 $T(n)=2T(n/2)+\Theta(n)$ 的解法（递归树）是后面分析一切分治算法的基础。第二卷我们会把这套"切两半"的结构推广到选择、几何、矩阵、多项式乘法上一一你会惊讶于它有多通用。