第 8 章　高效排序

本章解决的问题：既然 $O(n \log n)$ 是天花板（7.4 节），那几种达到它的排序算法各有什么脾气？以及真实工程中到底该用哪个。

8.1　归并排序：稳定且可预测

学习目标：学完本节，你能

• 手写归并排序，并说清"合并两个有序段"的关键操作；
• 用每层工作量 × 层数推导出 $O(n \log n)$；
• 解释为什么归并排序的比较次数几乎与输入无关 —— 以及这个性质的价值和代价。

先修：2.4（分治）、7.3（逆序对）。 固定术语：归并排序、合并、自顶向下、辅助空间。 环境与版本：.NET 8 / C# 12。 预计阅读：32 分钟。

一、直觉：两摞已经排好的牌

归并排序的全部内容，就是一个操作：把两个已经排好序的段，合并成一个有序段。

想象桌上有两摞牌，各自已经从小到大排好。要把它们合成一摞有序的：

看两摞的顶部，谁小就把谁拿走，放到结果里。

就这么简单。重复到两摞都拿完为止。

左摞: 1 4 7        右摞: 2 3 9
      ↓                  ↓
比较 1 和 2 -> 取 1   左摞: 4 7      右摞: 2 3 9     结果: 1
比较 4 和 2 -> 取 2   左摞: 4 7      右摞: 3 9       结果: 1 2
比较 4 和 3 -> 取 3   左摞: 4 7      右摞: 9         结果: 1 2 3
比较 4 和 9 -> 取 4   左摞: 7        右摞: 9         结果: 1 2 3 4
比较 7 和 9 -> 取 7   左摞: (空)     右摞: 9         结果: 1 2 3 4 7
左摞空了 -> 把右摞剩下的全部接上                      结果: 1 2 3 4 7 9

这个操作是 $O(m + n)$（$m$、$n$ 是两段的长度）—— 每个元素只看一次。

归并排序就是把这个操作递归地用起来：

1. 切开：把数组从中间分成两半
2. 解决：递归地把两半各自排好序
3. 合并：把两个有序的半边合并起来

这正是 2.4 节的分治三步。

二、实现

/// <summary>
/// 合并两个已经有序的段：a[lo..mid] 和 a[mid+1..hi]。
/// 这是归并排序的核心操作 —— 顺手统计比较次数，并在需要时统计逆序对。
/// </summary>
static void Merge(int[] a, int lo, int mid, int hi, ref long cmp, ref long inversions, bool countInversions)
{
    int[] temp = new int[hi - lo + 1];
    int i = lo, j = mid + 1, k = 0;

    while (i <= mid && j <= hi)
    {
        cmp++;
        if (a[i] <= a[j])                 // 注意 <= ：相等时优先取左边，保证【稳定】
        {
            temp[k++] = a[i++];
        }
        else
        {
            // 顺带数逆序对：a[i] > a[j]，说明 a[i..mid] 这 (mid - i + 1) 个元素都比 a[j] 大
            if (countInversions) inversions += mid - i + 1;
            temp[k++] = a[j++];
        }
    }

    while (i <= mid) temp[k++] = a[i++];
    while (j <= hi) temp[k++] = a[j++];

    Array.Copy(temp, 0, a, lo, temp.Length);
}

static void MergeSort(int[] a, int lo, int hi, ref long cmp, ref long inversions, bool countInversions)
{
    if (lo >= hi) return;                              // 基准情形：只剩 0 或 1 个元素

    int mid = lo + (hi - lo) / 2;                      // 这样写可以避免 lo+hi 溢出
    MergeSort(a, lo, mid, ref cmp, ref inversions, countInversions);
    MergeSort(a, mid + 1, hi, ref cmp, ref inversions, countInversions);
    Merge(a, lo, mid, hi, ref cmp, ref inversions, countInversions);
}

四个值得注意的细节：

1. if (a[i] <= a[j]) 用 <= —— 相等时优先取左边的元素。这就是归并排序稳定的原因（7.2 节）。改成 < 就会变成不稳定。
2. mid = lo + (hi - lo) / 2 而不是 (lo + hi) / 2 —— 后者在 lo 和 hi 都很大时会整数溢出。
3. 需要一个 temp 临时数组 —— 这是归并排序最大的代价。它是额外 $O(n)$ 空间。
4. if (lo >= hi) return; —— 0 个或 1 个元素天然有序，直接返回。

三、复杂度推导：每层工作量 × 层数

用 2.4 节学过的方法：

$$T(n) = \underbrace{2T(n/2)}{\text{递归排两半}} + \underbrace{O(n)}{\text{合并}}$$

层数：$n$ 每次减半，到规模 1 需要 $\log_2 n$ 层。

总复杂度 $= n \times \log_2 n = O(n \log n)$。

关键点：每一层的工作量都是 $n$，不随层数增加而减少。

这正是 2.4 节说的"分治该有的样子" —— 每层都干满活，层数才是 $\log n$。

对比 2.4 节的"分治求最大值"（$T(n) = 2T(n/2) + O(1)$）：那一版的合并太便宜，每层工作量递减，总和还是 $O(n)$ —— 白切。

关于辅助空间：Merge 里每次都要 new int[hi - lo + 1]。

• 每一层的临时数组加起来是 $O(n)$
• 但递归栈上同时存在的只有 $\log n$ 层
• 所以总空间是 $O(n)$（不是 $O(n \log n)$）

优化：生产级实现会在排序开始前分配一个和原数组等大的临时数组，反复复用 —— 避免每层都分配内存（这会带来 GC 压力）。

本节的实现为了清晰，每次合并都新建数组。

四、实测：归并排序的"性格"

实验一：和插入排序对比

  输入         |       归并排序比较 |         插入排序比较 | 谁更快
------------------------------------------------------------------------------
  随机         |        1,536,163 |    2,503,074,803 | 归并快 1,629.4 倍
  已排序       |          853,904 |           99,999 | 插入快 8.5 倍  <- 注意！
  完全逆序     |          815,024 |    4,999,950,000 | 归并快 6,134.7 倍
  近乎有序     |        1,184,174 |        6,780,423 | 归并快 5.7 倍

注意第二行 —— 这是一个必须看清的结果：

在"已排序"的数据上，插入排序只比较了 99,999 次（$n-1$），比归并排序的 853,904 次快了 8.5 倍！

因为插入排序在已排序数据上是 $O(n)$，而归并排序永远是 $O(n \log n)$。

"渐进复杂度更优"不等于"任何情况下都更快"。

这是 1.3 节（最好/最坏/平均）和 7.1 节（插入排序的 $O(n)$ 特性）的又一次呼应。

工程含义：如果你的数据大概率已经有序，插入排序可能是更好的选择 —— 这听起来很荒谬（$O(n^2)$ 的算法打赢 $O(n \log n)$ 的），但数据说明了一切。

后面会看到，工业级排序算法正是这么做的：它们在递归到小数组时切换到插入排序。

实验二：比较次数几乎与输入无关

           n |             随机 |            已排序 |           完全逆序 |      n*log2(n)
----------------------------------------------------------------------------
    10,000 |        120,433 |         69,008 |         64,608 |        132,877
    20,000 |        260,829 |        148,016 |        139,216 |        285,754
    40,000 |        561,746 |        316,032 |        298,432 |        611,508
    80,000 |      1,203,785 |        672,064 |        636,864 |      1,303,017

每一行的三个数字都在同一个量级 —— 随机、已排序、完全逆序，差异最多 2 倍（而且有序/逆序反而更快，因为合并时一半几乎不用比较）。

对比 7.1 节的插入排序：它在不同输入下的比较次数差了 150 倍。

这就是归并排序最大的特点，也是它最值钱的地方：

它的性能是可预测的。 不管用户给你什么数据 —— 已排序的、逆序的、全是一样的、还是精心构造的 —— 它都在 $O(n \log n)$ 这个量级。

在工程上，"可预测"往往比"平均更快"更有价值：

• 你能放心地给 SLA 承诺
• 不用担心某个用户上传一份特殊数据就把服务拖垮
• 不用做"最坏情况"的额外防御（比如 8.2 节要讲的随机化）

五、附带技能：$O(n \log n)$ 数逆序对

7.3 节的练习留了一个问题：怎么快速数逆序对？

答案就在 Merge 里那一行：

if (countInversions) inversions += mid - i + 1;

原理：合并时，左边段 a[i..mid] 和右边段 a[mid+1..hi] 各自都是有序的。

如果 a[i] > a[j]，那么：

• a[i] > a[j] ✓
• a[i+1] >= a[i] > a[j] ✓
• ……
• a[mid] >= a[i] > a[j] ✓

左边从 i 到 mid 的所有元素，都比 a[j] 大 —— 它们和 a[j] 都构成逆序对。

所以一次比较就能数出 mid - i + 1 个逆序对，而不是一个一个数。

实测：

  小例子 [5, 2, 4, 1, 3]: 逆序对 = 7（7.3 节手工数出来也是 7）

  归并 vs 暴力数逆序对（n = 5,000）：
    暴力 O(n^2)     :    6,258,189 个   （耗时   10.38 ms）
    归并 O(n log n) :    6,258,189 个   （耗时    0.24 ms）
    结果一致 = True，归并快 44 倍

结果完全一致，但快了 44 倍（而且 $n$ 越大差距越大）。

这是一个"顺带解决问题"的漂亮例子：归并排序在合并时本来就要比较元素，而"数逆序对"需要的正是这个信息。

没有增加任何额外的渐进复杂度 —— 只是在已有的比较上多了一次加法。

这类"顺手把另一个问题也解决了"的机会在算法设计中很常见：比如 8.4 节的基数排序顺带利用了计数排序的稳定性，5.4 节的单调队列顺带维护了窗口最值。

有什么用？

逆序对数量可以衡量"数据有多乱"：

• 协同过滤：两个用户的评分序列有多不一致
• 数据质量监控：一个本该递增的序列，逆序对突然增多说明可能有问题
• 相似度比较：两个排序之间的"距离"（Kendall tau 距离）

六、归并排序的完整评价

归并排序还有一个杀手级应用：外部排序。

当数据大到内存装不下时（比如排一个 100 GB 的文件），思路是：

1. 把文件切成若干块，每块读进内存排好序，写回磁盘（这些块叫"归并段"）
2. 对这些归并段做多路归并，逐段合并成最终结果

这个"归并"的过程正是归并排序的核心操作，而且它天然适合顺序读写磁盘。

数据库的 ORDER BY、大数据框架的 shuffle、Linux 的 sort 命令处理大文件 —— 底层都是外部归并排序。

七、练习

练习 8.1.1（手写合并） 把 [1, 4, 7, 9] 和 [2, 3, 5, 8] 合并成一个有序数组。写出每一步的比较和取值过程，并统计总共比较了几次。

练习 8.1.2（推导） 用"每层工作量 × 层数"的方法，推导归并排序的空间复杂度。 (a) 递归栈的深度是多少？ (b) 每一层的临时数组总大小是多少？ (c) 所以总的额外空间是多少？为什么不是 $O(n \log n)$？

练习 8.1.3（判断） 判断对错并说明理由： (a) 归并排序在任何输入下都比插入排序快。 (b) 归并排序的比较次数是固定的，和输入无关。 (c) 归并排序的空间复杂度是 $O(n \log n)$。

练习 8.1.4（改进） 本节的 Merge 每次调用都 new int[hi - lo + 1]。在一个 100 万元素的排序中，这会分配多少次数组？总共分配多少内存？ (a) 算一下具体数字。 (b) 怎么改进？ (c) 改进后空间复杂度变了吗？

练习 8.1.5（挑战·三路归并） 归并排序把数组分成两半。能不能分成三份，做"三路归并"？ (a) 递推式会变成什么样？ (b) 用"每层工作量 × 层数"分析，复杂度是多少？ (c) 实际会比二路归并更快吗？为什么？

八、练习答案

8.1.1

左段 [1, 4, 7, 9]，右段 [2, 3, 5, 8]：

总共比较了 7 次。

注意最后一步：右段空了之后，左段剩下的元素直接全部接上，不需要再比较。

这是合并操作的一个性质：当一段耗尽时，另一段剩下的元素已经是最大的那批，直接搬就行。

推论：最坏情况下需要比较 $m + n - 1$ 次（每次只消耗一个元素）；最好情况只需要 $\min(m, n)$ 次（一段很快耗尽）。

8.1.2

(a) 递归深度 = $\log_2 n$。

因为每次把规模减半，从 $n$ 到 1 需要 $\log_2 n$ 层。

(b) 每一层的临时数组总大小是 $O(n)$。

• 第 0 层：一次合并，临时数组大小 $n$
• 第 1 层：两次合并，各 $n/2$，合计 $n$
• 第 $k$ 层：$2^k$ 次合并，各 $n/2^k$，合计 $n$

(c) 总空间是 $O(n)$（而不是 $O(n \log n)$）。

关键在于"同时活着"的临时数组有多少：

• 每一层的临时数组加起来是 $n$，这没错
• 但它们不是同时存在的！

具体的执行顺序是深度优先：

MergeSort(0, n)            <- 进入
  MergeSort(0, n/2)        <- 先处理左半，一路递归下去
    ...
      合并(规模2)   <- 分配 temp[2]，合并完立即释放
      合并(规模4)   <- 分配 temp[4]，合并完立即释放
    ...
  MergeSort(n/2, n)        <- 左半全部处理完，才开始右半

执行到"最深处的合并"时，只有那一个 temp 还活着（大小是 2、4、8……）。上一层的 temp 早就 return 了，已经被 GC 回收。

所以在任意时刻，同时存在的临时数组总大小是：

$$n/2^k + n/2^{k-1} + \cdots + n/2 + n < 2n = O(n)$$

（沿着一条从根到叶的路径，各层的未完成合并的临时数组）

这里有个容易搞错的点：如果实现里先把所有 temp 都分配好再递归（比如传入预分配的数组），那就是 $O(n \log n)$ 了。

本节的实现是"每次合并时分配、合并完就没了"，所以是 $O(n)$。

8.1.3

• (a) 错。 本节实测就是反例：已排序数据上，插入排序比归并排序快 8.5 倍（99,999 次比较 vs 853,904 次）。

  原因：插入排序在已排序数据上是 $O(n)$，而归并排序永远是 $O(n \log n)$。

  正确的说法："归并排序在最坏情况和随机情况下远优于插入排序" —— 但最好情况不是它的强项。

• (b) 错（不准确）。 是"几乎与输入无关"，不是"完全固定"。

  从实验二的表看：$n = 80{,}000$ 时，随机是 1,203,785 次，而已排序只有 672,064 次 —— 差了将近一倍。

  原因：合并时，如果一段的元素全部小于另一段，那么那一段耗尽后，剩下的直接搬走，不需要再比较。已排序的数组恰好是这种"一边倒"的情况。

  但不管哪种情况，都在 $O(n \log n)$ 量级内 —— 这才是"可预测"的真正含义。

• (c) 错。 是 $O(n)$（见练习 8.1.2 的推导）。

  常见误解的来源：有人会想"每一层都要 $n$ 的空间，有 $\log n$ 层，所以是 $n \log n$"。

  但这个推理错了：那些临时数组不是同时存在的。深度优先的执行方式决定了：任意时刻只有一条"递归路径"上的几个数组活着，总大小 $< 2n$。

8.1.4

(a) 归并排序的递归树有 $n - 1$ 个内部节点（每次合并产生一个），所以会分配 $n - 1$ 次数组。

对于 $n = 10^6$：约 100 万次数组分配。

总分配的内存量：每次合并的临时数组大小之和 = 每一层 $n$ × 层数 = $n \log_2 n$。

$$10^6 \times 20 = 2 \times 10^7 \text{ 个 int} = 80 \text{ MB}$$

总共分配了约 80 MB 的内存（虽然每次用完就回收）。

这就是问题所在：虽然空间复杂度是 $O(n)$，但实际的内存分配总量是 $O(n \log n)$，而且产生了 100 万次 GC 压力。

GC 压力比内存占用更致命 —— 频繁分配会触发垃圾回收，造成不可预测的停顿。

(b) 改进：预分配一个临时数组，全程复用。

static void MergeSort(int[] a)
{
    int[] temp = new int[a.Length];        // 只分配一次
    Sort(a, temp, 0, a.Length - 1);
}

static void Sort(int[] a, int[] temp, int lo, int hi)
{
    if (lo >= hi) return;
    int mid = lo + (hi - lo) / 2;
    Sort(a, temp, lo, mid);
    Sort(a, temp, mid + 1, hi);
    Merge(a, temp, lo, mid, hi);
}

static void Merge(int[] a, int[] temp, int lo, int mid, int hi)
{
    // 把数据复制到 temp 的对应位置，再合并回 a
    Array.Copy(a, lo, temp, lo, hi - lo + 1);

    int i = lo, j = mid + 1;
    for (int k = lo; k <= hi; k++)
    {
        if (i > mid) a[k] = temp[j++];                          // 左半用完了
        else if (j > hi) a[k] = temp[i++];                      // 右半用完了
        else if (temp[j] < temp[i]) a[k] = temp[j++];           // 注意这里是 < ：取右边
        else a[k] = temp[i++];                                  // 相等或左边小：取左边（稳定）
    }
}

改进后：只分配 1 次数组，而不是 $n - 1$ 次。

(c) 空间复杂度不变，仍是 $O(n)$。

但"分配总量"从 $O(n \log n)$ 降到 $O(n)$，"分配次数"从 $O(n)$ 降到 $O(1)$。

这个区别很重要：

• 空间复杂度衡量的是"峰值占用"—— 改进前后都是 $O(n)$
• 分配总量衡量的是"GC 压力"—— 改进前后差了一个 $\log n$ 因子

这就是为什么"大 O 相同"的实现，实际性能可能差很多。 生产级的归并排序一定会做这个优化。

8.1.5

(a) 递推式：

$$T(n) = 3T(n/3) + O(n)$$

（分成三份，每份规模 $n/3$，合并三个有序段的代价是 $O(n)$）

(b) 复杂度分析：

层数：$\log_3 n$。

$$T(n) = n \times \log_3 n = O(n \log n)$$

量级不变（换底公式：$\log_3 n = \frac{\log_2 n}{\log_2 3} \approx 0.63 \log_2 n$）。

更一般地：$T(n) = aT(n/a) + O(n)$ 对任何常数 $a$ 都是 $O(n \log n)$。

因为每层工作量恒为 $n$，层数是 $\log_a n$，而 $\log_a n$ 和 $\log_2 n$ 只差一个常数因子。

(c) 实际会比二路归并更慢。

三个原因：

1. 合并三段的常数更大。 合并两个有序段时，每次比较是"二选一"；合并三段是"三选一"，需要两次比较才能确定取哪个（先比前两个，再和第三个比）。每次取元素的代价上升了。

2. 层数减少的收益有限。 层数从 $\log_2 n$ 降到 $\log_3 n$，只是乘以 0.63 —— 少了 37% 的层数。但每次合并的成本增加了更多。

3. 缓存不友好。 三路归并要同时维护三个指针，访问三个不同的内存区域。而二路归并只需要维护两个 —— 对 CPU 缓存更友好。

理论上更"平衡"的分法（三路、四路）在常数上反而更差。 这就是为什么实际的归并排序都用二路。

但注意：在外部排序（数据在磁盘上）的场景下，多路归并是必要的 —— 因为磁盘的瓶颈是"读取次数"而不是"比较次数"。用 $k$ 路归并能把"读取轮数"从 $\log_2(\text{段数})$ 降到 $\log_k(\text{段数})$，大幅减少磁盘 I/O。

同一个算法，在内存里和磁盘上的最优参数完全不同 —— 因为瓶颈变了。这是 8.5 节要反复强调的主题。

九、常见错误

十、本节总结

1. 归并排序 = 分治 + 合并两个有序段。核心操作"取两者中较小的"是 $O(m+n)$。
2. 复杂度 $O(n \log n)$：每层工作量恒为 $n$，共 $\log n$ 层。
3. 最大特点是可预测：最好/最坏/平均都是 $O(n \log n)$，实测四种输入下比较次数都在同一量级。
4. 但它不是"总是更快"：已排序数据上插入排序比它快 8.5 倍（$O(n)$ vs $O(n \log n)$）。渐进复杂度更优 ≠ 任何情况都更快。
5. 它是稳定的：合并时用 <=，相等优先取左边。
6. 额外空间 $O(n)$，且要注意"分配总量 vs 峰值占用"的区别 —— 预分配复用能把分配次数从 $O(n)$ 降到 $O(1)$。
7. 顺带能数逆序对：合并时一次比较能数出 mid - i + 1 个逆序对，实测比暴力快 44 倍。
8. 外部排序的基石：数据大到内存装不下时，靠多路归并处理。

下一节衔接：归并排序什么都好 —— 稳定、可预测、$O(n \log n)$ —— 但它有一个"缺点"：需要 $O(n)$ 的额外空间。下一节的快速排序原地排序，平均速度更快，但代价是最坏情况会退化到 $O(n^2)$。实测会让你看到这个退化有多可怕。

状态外显

{
  "book": "数据结构与算法自学：从工程直觉到复杂度思维",
  "section": "8.1",
  "title": "归并排序：稳定且可预测",
  "covered": [
    "「合并两个有序段」的直觉与 O(m+n) 代价",
    "归并排序完整实现（含 <= 保证稳定、mid 防溢出）",
    "T(n)=2T(n/2)+O(n) 的逐层推导",
    "空间 O(n) 而非 O(n log n) 的分析（临时数组不同时存在）",
    "实测：已排序数据上插入排序反而快 8.5 倍",
    "比较次数几乎与输入无关的实测（四种输入同量级）",
    "O(n log n) 数逆序对的技巧与 44 倍加速",
    "分配总量 O(n log n) vs 峰值空间 O(n) 的区别与预分配优化",
    "外部排序的原理与多路归并"
  ],
  "unresolved": [
    "快速排序留到 8.2",
    "堆排序留到 8.3",
    "内省排序留到 8.5"
  ],
  "canonical_terms": {
    "归并排序": "分治：递归排两半，再合并两个有序段",
    "合并": "把两个有序段合成一个有序段，O(m+n)",
    "辅助空间": "算法运行所需的额外内存，归并排序为 O(n)"
  },
  "symbols_units": {},
  "assumptions": [
    "读者已掌握 2.4 的分治与 7.2 的稳定性",
    "读者理解递归的执行顺序（深度优先）"
  ],
  "word_count_actual": 3380,
  "checks": [
    "C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑，输出见正文",
    "项目文件：99-tools/samples/Ch08/Sec81/",
    "四种输入的比较次数、逆序对数（与暴力结果一致）均为实测",
    "练习 8.1.1 的合并过程已手工推演（7 次比较）",
    "术语写法与 glossary.md 一致"
  ],
  "known_issues": [
    "初版输出把「插入排序更快」显示为「归并快 0.1 倍」，难以理解；已改为显式的「插入快 8.5 倍 <- 注意！」并把这一反直觉结论写成正文要点"
  ],
  "next": "8.2 快速排序：平均最快，最坏要防"
}