【一周一算法】第三周：归并排序

🧮 一周一个算法 · 第 3 周

归并排序（Merge Sort）——分治思想的第一次登场

“Divide and Conquer” —— 分而治之，算法的灵魂。 归并排序不仅是高效排序算法的代表，更是理解递归、复杂度分析与算法分层结构的最佳入口。

---

🧭 一、引言：如何让"排序"并行起来？

假设你要给一副 1000 张的扑克牌排序。 最直观的想法是一个人从头到尾慢慢排好（冒泡/插入）。 但如果你把 1000 张牌分成 4 份，四个人同时各自排好，再合并呢？

✅ 每人工作量变少； ✅ 最后只需合并四份有序牌； ✅ 这就是归并排序的核心思想：

Divide（划分） → Conquer（解决） → Combine（合并）

---

🧩 二、算法思想

🌱 思想概括：

1. 将数组一分为二；
2. 对左右两部分分别递归排序；
3. 将两个有序子数组合并为一个新的有序数组。

图示说明：

原数组: [38, 27, 43, 3, 9, 82, 10]

分解:
[38, 27, 43, 3]       [9, 82, 10]
   ↓                      ↓
[38, 27] [43, 3]      [9, 82] [10]
   ↓        ↓           ↓       ↓
[27, 38] [3, 43]      [9, 82] [10]
   ↓        ↓           ↓       ↓
   [3, 27, 38, 43]     [9, 10, 82]
         ↓                ↓
     [3, 9, 10, 27, 38, 43, 82]

---

⚙️ 三、伪代码

procedure MergeSort(A, left, right):
    if left >= right:
        return
    mid ← (left + right) / 2
    MergeSort(A, left, mid)
    MergeSort(A, mid + 1, right)
    Merge(A, left, mid, right)

---

🔧 合并（Merge）操作

将两个有序子数组 [left..mid] 和 [mid+1..right] 合并成一个新的有序数组。

procedure Merge(A, left, mid, right):
    L ← A[left..mid]
    R ← A[mid+1..right]
    i ← 0, j ← 0, k ← left
    while i < len(L) and j < len(R):
        if L[i] ≤ R[j]:
            A[k] ← L[i]; i ← i + 1
        else:
            A[k] ← R[j]; j ← j + 1
        k ← k + 1
    // 拷贝剩余元素
    while i < len(L): A[k++] ← L[i++]
    while j < len(R): A[k++] ← R[j++]

---

💻 四、C++ 实现

#include <iostream>
#include <vector>

void merge(std::vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    std::vector<int> L(n1), R(n2);

    for (int i = 0; i < n1; ++i)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; ++j)
        R[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;

    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k++] = L[i++];
        } else {
            arr[k++] = R[j++];
        }
    }

    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

void mergeSort(std::vector<int>& arr, int left, int right) {
    if (left >= right) return;

    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

int main() {
    std::vector<int> arr = {38, 27, 43, 3, 9, 82, 10};
    mergeSort(arr, 0, arr.size() - 1);

    std::cout << "排序结果：";
    for (int num : arr) std::cout << num << " ";
    std::cout << std::endl;
}

输出：

排序结果：3 9 10 27 38 43 82

---

📈 五、复杂度分析（数学视角）

1️⃣ 时间复杂度（递归关系式）

归并排序的运行时间满足：

$$T(n) = 2T\left(\frac{n}{2}\right) + O(n)$$

解释：

• $2T(n/2)$：递归两次处理子数组；
• $O(n)$：合并操作。

使用 主定理（Master Theorem）：

$$T(n) = aT(n/b) + f(n)$$

其中 $a = 2$, $b = 2$, $f(n) = n$

由于 $n^{\log_b a} = n^{\log_2 2} = n^1$， 且 $f(n) = O(n)$， 满足第二种情况：

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

✅ 最终结果：

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

---

2️⃣ 空间复杂度

需要额外数组存放临时合并结果：

$$S(n) = O(n)$$

---

3️⃣ 稳定性分析

✅ 稳定：当 $L[i] = R[j]$ 时优先拷贝左侧元素。

---

🔢 六、数学深入：为什么是 $O(n \log n)$？

我们从递归树角度理解：

每一层的合并代价都是 n：

第0层：1个子问题，大小n → 代价 n
第1层：2个子问题，大小n/2 → 代价 2*(n/2) = n
第2层：4个子问题，大小n/4 → 代价 4*(n/4) = n
...
总层数 ≈ log₂n

总代价：

$$n + n + n + \cdots + n = n \log_2 n$$

因此：

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

---

🚀 七、工程特性与实践优化

优化方向	思想	效果
小区间改用插入排序	当子数组长度 < 16，用插入排序更快	CPU Cache友好
原地合并优化	避免临时数组	减少空间开销（但实现复杂）
多线程归并	两个子问题并行	大幅提高多核性能
外部排序（磁盘归并）	适合大数据集	I/O 优化

---

🧠 八、思考与练习

1. 为什么归并排序在链表排序中表现非常优？ （提示：合并链表可以 $O(1)$ 操作，无需移动内存）

2. 若数组长度是 1024，递归深度是多少？ （提示：$\log_2 1024 = 10$）

3. 请尝试实现 迭代版（非递归版） 归并排序。

4. 你能在 merge() 函数中只用一个缓冲区完成左右合并吗？

---

🌱 九、延伸阅读

• 《算法导论》第 2.3 章：归并排序

• 《计算机程序设计艺术（TAOCP）》卷 3 §5.2.4

• LeetCode 推荐题目：

  • #148. Sort List（链表归并排序）
  • #912. Sort an Array

---

✨ 十、总结

指标	说明
时间复杂度	$O(n \log n)$
空间复杂度	$O(n)$
稳定性	✅ 稳定
是否原地排序	❌ 否（需辅助数组）
适用场景	大数据、链表排序、外部排序

“归并排序是算法的第一次哲学思考—— 把问题拆分成能解决的小问题，再组合回答案。”

---

🔜 下周预告（第 4 周）

快速排序（Quick Sort）——“分治"遇上"随机” 我们将看到：相同的分治思想，如何在"期望复杂度 $O(n \log n)$"中跑得更快。

---