深入理解归并排序：C++实现详解

今天我们来聊聊经典的排序算法——归并排序（Merge Sort）。归并排序是一种高效的、分治思想的排序算法，它的时间复杂度是O(n log n)，在处理大数据时特别稳定。如果你是个C++爱好者，或者正在学习算法，这篇文章会带你一步步剖析一段完整的归并排序代码实现。

归并排序的核心思想是“分而治之”：先把数组分成小块排序，然后合并有序的部分。听起来简单，但实现起来有不少细节需要注意。下面，我们就来看看这段代码是怎么工作的。我会用Markdown格式逐步拆解，每部分配上解释和代码片段，便于你复制运行。

什么是归并排序？

归并排序是一种递归算法：

• 分（Divide）：将数组分成两半，直到每个子数组只有一个元素（已排序）。
• 治（Conquer）：递归排序子数组。
• 合（Merge）：将两个有序子数组合并成一个有序数组。

优点：稳定排序（相同元素顺序不变），适合链表等结构。缺点：需要额外空间O(n)来辅助合并。

现在，让我们进入代码分析。这段代码使用向量（vector）存储数组，实现了标准的自顶向下归并排序。

代码整体结构

代码包括三个主要部分：

• merge 函数：负责合并两个有序子数组。
• mergesort 函数：递归分治排序。
• main 函数：读取输入、调用排序、输出结果。

完整代码如下（我稍作格式化，便于阅读）：

#include <iostream>
#include <vector>
using namespace std;

void merge(vector<int>& a, int l, int mid, int r) {
    vector<int> left(a.begin() + l, a.begin() + mid + 1);
    vector<int> right(a.begin() + mid + 1, a.begin() + r + 1);
    left.push_back(INT_MAX);
    right.push_back(INT_MAX);
    int i = 0, j = 0;
    for (int k = l; k <= r; ++k) {
        if (left[i] <= right[j]) {
            a[k] = left[i++];
        } else {
            a[k] = right[j++];
        }
    }
}

void mergesort(vector<int>& a, int l, int r) {
    if (l >= r) return;
    int mid = (l + r) / 2;
    mergesort(a, l, mid);
    mergesort(a, mid + 1, r);
    merge(a, l, mid, r);
}

int main() {
    int n = 0;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    mergesort(a, 0, n - 1);
    for (int i = 0; i < n; ++i) {
        cout << a[i];
        if (i < n - 1) cout << " ";
    }
    cout << "\n";
    return 0;
}

详细函数剖析

1. merge 函数：合并有序子数组

这是归并排序的“合”部分。函数接收数组引用 a，以及左右边界 l、mid、r。

• 步骤：

  1. 创建两个临时向量：left（从 l 到 mid）和 right（从 mid+1 到 r）。
  2. 在每个临时向量末尾添加哨兵值 INT_MAX（最大整数），避免边界检查（巧妙技巧！）。
  3. 使用两个指针 i 和 j 比较并合并元素回原数组 a。

• 为什么用哨兵？ 防止其中一个子数组先耗尽时，还要检查另一个的剩余元素。这样简化了代码。

代码片段重点：

vector<int> left(a.begin() + l, a.begin() + mid + 1);
vector<int> right(a.begin() + mid + 1, a.begin() + r + 1);
left.push_back(INT_MAX);
right.push_back(INT_MAX);

合并循环：

int i = 0, j = 0;
for (int k = l; k <= r; ++k) {
    if (left[i] <= right[j]) {
        a[k] = left[i++];
    } else {
        a[k] = right[j++];
    }
}

注意：这里是稳定排序，因为当相等时优先取左边元素。

2. mergesort 函数：递归分治

这是“分”和“治”的核心。函数递归调用自身，直到 l >= r（基线条件：单个元素已排序）。

• 步骤：
  1. 计算中点 mid = (l + r) / 2（注意：整数除法）。
  2. 递归排序左半部分 mergesort(a, l, mid)。
  3. 递归排序右半部分 mergesort(a, mid + 1, r)。
  4. 调用 merge 合并。

代码简洁有力：

if (l >= r) return;
int mid = (l + r) / 2;
mergesort(a, l, mid);
mergesort(a, mid + 1, r);
merge(a, l, mid, r);

提示：在实际应用中，如果担心整数溢出，可以用 mid = l + (r - l) / 2。

3. main 函数：入口与I/O

• 读取输入：先读数组大小 n，然后读 n 个整数到向量 a。
• 调用排序：mergesort(a, 0, n - 1)。
• 输出：遍历数组，空格分隔，最后换行。

这是一个标准的命令行程序。你可以编译运行，比如输入：

5
3 1 4 1 5

输出：

1 1 3 4 5

性能分析

• 时间复杂度：O(n log n) —— 分治层数 log n，每层合并 O(n)。
• 空间复杂度：O(n) —— 临时向量。
• 适用场景：大数据排序、外部排序（磁盘文件）。

相比快速排序，归并排序更稳定，但快排平均更快（不过最坏O(n^2)）。

常见优化与变体

• 自底向上归并：非递归版本，使用循环从子数组大小1开始合并。
• 混合排序：小数组用插入排序（减少递归开销）。
• 多线程：递归分支可并行化。

如果你想实验，试试修改代码处理浮点数或字符串！

结语

归并排序是算法面试常客，理解它能帮你掌握分治思想。