归并排序：像整理两堆扑克牌一样排好序

假如你有两堆扑克牌，每堆都已经从小到大排好序了。现在你想把它们合并成一堆有序的牌，你会怎么做？很简单：每次比较两堆最上面的牌，把较小的那张拿下来放到新堆里，然后继续，直到全部拿完。这就是归并排序中最重要的“合并”步骤。

归并排序（Merge Sort）是典型的分治算法。它的工作流程可以分为三步：

分解：把待排序的数组从中间切成两半，然后分别对左半和右半递归地继续切分，直到每一部分只剩一个元素（一个元素天然有序）。
解决：当子数组长度为1时，已经有序，不需要额外操作。
合并：把两个已经有序的子数组合并成一个更大的有序数组。合并时，用两个指针分别指向两个子数组的开头，比较大小，依次取较小的元素放入结果。

整个过程就像先拆散一堆杂牌，再一张一张按顺序垒起来。

什么是归并排序？

归并排序是一种稳定的、基于分治思想的排序算法。它把大问题分解成小问题，先解决小问题，再把结果合并起来。特别适合处理数据量很大、或者要求排序结果稳定的场景。比如考试后老师要把两个已经按成绩排好名次的班级名单合并成一个年级总名单，就可以用归并排序的思路。

归并排序的步骤详解

1. 分解（Divide）

我们要把一个乱序的数组不断对半切分，直到每个小段只有一个元素。因为一个元素本身就是有序的，不需要再拆了。

生活中的例子：你有8张杂乱的卡片，先分成两堆各4张，再分别把每堆分成两堆各2张，最后每堆只剩1张。这样你就有了8个“有序小堆”，每堆只有一张牌。

2. 解决（Conquer）

当子数组长度为1时，已经有序，什么都不用做。

3. 合并（Merge）

这是最核心的一步。把两个有序的小数组合并成一个更大的有序数组。

生活中的例子：你手里有两堆已经排好序的牌（比如左边是1,3,5，右边是2,4,6）。你会这样做：

比较最上面两张：1和2，1更小，拿1放到新堆。
现在左边剩下3,5，右边还有2,4,6。比较3和2，2更小，拿2。
继续比较3和4，拿3；比较5和4，拿4；比较5和6，拿5；最后右边剩下6，直接拿。
最终新堆是1,2,3,4,5,6。

对应到代码中，我们使用两个指针分别指向左右子数组的开头，依次取较小的元素放入原数组的对应位置。

生活中的更多例子

场景	说明
整理试卷	老师把两个班级的试卷按学号排好，合并成一个年级的试卷，就是归并合并。
零花钱记账	你每天记录零花钱支出，每周一和周三分别记了两张有序的账单，周末把它们合并成一张总账单。
排队买零食	两个队伍都已经按身高排好，现在要合并成一个队伍，每次从两个队首挑更矮的人到新队伍。

合并过程详解（图解结合代码）

假设我们要合并两个有序子数组：左子数组 = [1, 3, 5]，右子数组 = [2, 4, 6]。

我们用临时数组 L 和 R 分别存储左右子数组的内容，然后比较 L[i] 和 R[j]，将小的放入原数组 arr[]。

步骤	L指针	R指针	比较结果	放入的元素	原数组状态
1	i=0(1)	j=0(2)	1<=2	1	[1]
2	i=1(3)	j=0(2)	3>2	2	[1,2]
3	i=1(3)	j=1(4)	3<=4	3	[1,2,3]
4	i=2(5)	j=1(4)	5>4	4	[1,2,3,4]
5	i=2(5)	j=2(6)	5<=6	5	[1,2,3,4,5]
6	i=3(越界)	j=2(6)	右边剩余	6	[1,2,3,4,5,6]

最后，当其中一个子数组取完后，把另一个子数组剩余的所有元素按顺序拷贝过去。

代码拆解：每个部分的作用

下面是完整的C++归并排序实现。核心函数有两个：merge负责合并两个有序区间，mergeSort负责递归分解。

#include <iostream>
using namespace std;

void merge(int arr[], int left, int mid, int right) {
    // 计算左右子数组的长度
    int n1 = mid - left + 1;  // 左半部分长度
    int n2 = right - mid;      // 右半部分长度
    
    // 创建临时数组存放左右子数组的内容
    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;  // 指向左子数组的当前元素
    int j = 0;  // 指向右子数组的当前元素
    int k = left; // 指向原数组要放置元素的位置

    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    // 如果左边还有剩余，全部拷过去
    while (i < n1) { arr[k] = L[i]; i++; k++; }
    // 如果右边还有剩余，全部拷过去
    while (j < n2) { arr[k] = R[j]; j++; k++; }
}

void mergeSort(int arr[], int left, int right) {
    if (left < right) {  // 只要区间内不止一个元素，就继续分解
        int mid = (left + right) / 2;  // 找到中间位置
        mergeSort(arr, left, mid);       // 递归排序左半部分
        mergeSort(arr, mid + 1, right);  // 递归排序右半部分
        merge(arr, left, mid, right);    // 合并两个有序部分
    }
}

int main() {
    int arr[] = {38, 27, 43, 3, 9, 82, 10};
    int n = sizeof(arr) / sizeof(arr[0]);  // 计算数组长度
    mergeSort(arr, 0, n - 1);
    cout << "排序结果: ";
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;
    return 0;
}

运行后输出：3 9 10 27 38 43 82。归并排序非常稳定，无论什么数据，速度都很有保障。

常见错误

新手在写归并排序时容易犯以下几个错误：

忘记递归终止条件：mergeSort 函数里必须写 if (left < right)，否则会无限递归下去，导致栈溢出。
合并时临时数组越界：临时数组 L 和 R 的大小必须正确，n1 = mid - left + 1，n2 = right - mid。如果写错，可能访问到未定义的内存。
合并循环的边界条件：while (i < n1 && j < n2) 这个同时循环结束后，要记得处理剩余的元素。很多人只写了主循环，忘记后面两个 while。
传入错误的参数：调用 mergeSort 时，左边界和右边界要正确。比如数组是 0 到 n-1，如果你不小心传成了 0 到 n，就会访问越界。
合并时覆盖了未处理的数据：使用临时数组时，先把左右子数组拷贝出来，再放回原数组。如果直接在原数组上操作，可能会打乱数据。

总结与相关指引

归并排序是分治算法的经典代表。它的时间复杂度稳定为 O(n log n)，空间复杂度为 O(n)（因为需要额外临时数组）。优点是稳定、速度快且不受输入数据影响；缺点是需要额外的内存空间。

如果你理解了归并排序，接下来可以学习：

快速排序：同样是分治思想，但不用额外空间。
逆序对问题：归并排序可以轻松求出数组中的逆序对数量。
外部排序：当数据量太大无法一次性加载到内存时，归并排序的思想可以用于磁盘文件的排序。

现在，你可以动手试试用归并排序整理自己的零花钱账单，或者把两个有序的好友列表合并成一个！

例题精讲