GESP 五级 第 07 讲：分治——归并排序与快速排序

本讲定位：五级的算法高峰。官方大纲的「分治算法」知识块只列了两个算法：归并排序和快速排序——说明这两个必须写得出、分析得清。2026 年 3 月五级真题中，判断题第 3 题考快排稳定性、第 5 题给出了归并求逆序对的代码片段。

对应官方大纲：五级知识块 7「分治算法」——归并排序算法、快速排序算法。同时综合运用知识块 2（复杂度估算）和知识块 6（递归）。

前置知识：四级第 05 讲（排序与稳定性）、五级第 06 讲（递归复杂度）、五级第 04 讲练习 5（合并两个有序链表）。

代码说明：本讲两个排序均已用 g++ 11.5 编译，并与 std::sort 随机对拍 1000 组验证通过；逆序对计数与 $O(n^2)$ 暴力对拍一致。

1. 分治思想

分治（Divide and Conquer）三步：

步骤 含义
分（Divide） 把原问题拆成若干个规模更小的同类子问题
治（Conquer） 递归解决子问题（小到边界时直接解决）
合（Combine） 把子问题的解合并成原问题的解

关键在”合”：分治能不能成立、复杂度是多少，全看合并这一步有多贵。

$$ T(n) = a\,T(n/b) + \underbrace{O(f(n))}_{\text{合并的代价}} $$

回顾五级第 06 讲的表：$T(n)=2T(n/2)+O(n) \Rightarrow O(n\log n)$。归并排序就是这个式子的化身。

2. 归并排序（Merge Sort）

2.1 思想

        [5, 2, 9, 1, 7, 3]
       /                  \        ← 分：从中间劈开
  [5, 2, 9]            [1, 7, 3]
     ↓ 递归排好            ↓ 递归排好
  [2, 5, 9]            [1, 3, 7]
       \                  /        ← 合：合并两个有序数组
        [1, 2, 3, 5, 7, 9]

“分”很简单（对半切），“合”是核心——把两个已排好序的数组合并成一个。

2.2 核心：merge（合并两个有序段）

这和五级第 04 讲练习 5「合并两个有序链表」是同一个算法。

const int MAXN = 100005;
int a[MAXN], tmp[MAXN];         // tmp 是辅助数组，必须有

// 合并 a[l..m] 和 a[m+1..r]（两段各自已有序）
void merge(int l, int m, int r) {
    int i = l, j = m + 1, k = l;
    while (i <= m && j <= r) {
        if (a[i] <= a[j]) tmp[k++] = a[i++];    // ★ <= 保证稳定性
        else              tmp[k++] = a[j++];
    }
    while (i <= m) tmp[k++] = a[i++];           // 左段剩余
    while (j <= r) tmp[k++] = a[j++];           // 右段剩余
    for (int t = l; t <= r; t++) a[t] = tmp[t]; // ★ 拷回原数组
}

三个要点：

  1. a[i] <= a[j] 取左边：相等时优先取左段的，这就是归并排序稳定的原因。改成 < 就不稳定了。
  2. 两个收尾 while 必不可少：一段走完后，另一段剩下的已经有序，直接搬过去。
  3. 最后要拷回 a，否则排序结果留在 tmp 里白干了。

2.3 主体

void mergeSort(int l, int r) {
    if (l >= r) return;                 // 边界：只剩 0 或 1 个元素，天然有序
    int m = l + (r - l) / 2;
    mergeSort(l, m);                    // 分 + 治：左半
    mergeSort(m + 1, r);                // 分 + 治：右半
    merge(l, m, r);                     // 合
}
// 调用：mergeSort(0, n-1);