归并排序详解：从分治思想到代码实现

重要

在常见排序算法中，归并排序是一种非常经典的方法。它的核心思想并不复杂，本质上就是两个字：分治。

一、什么是归并排序

归并排序（Merge Sort）是一种基于分治思想的排序算法。

它的基本思路是：

把当前区间不断从中间分成两半
先让左半部分有序
再让右半部分有序
最后把两个有序部分合并成一个整体有序的区间

也就是说，归并排序并不是一上来就“直接排整个数组”，而是先把大问题拆成小问题，等小问题解决后，再一步步合并回来。

二、归并排序的整体思路

假设我们有一个数组：

[5, 2, 4, 1, 3]

归并排序会这样处理：

先把整个数组从中间分开
左边继续分，右边也继续分
一直分到每个区间只剩下一个数
因为单个元素天然有序，所以再开始两两合并
合并成更大的有序区间
最终整个数组有序

可以简单理解为：

先拆到不能再拆
再从底往上合并

这就是典型的分治过程。

三、代码模板

先看这段经典实现：

void merge_sort(int q[], int l, int r) {
    if (l >= r) return;

    int mid = l + r >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r) {
        if (q[i] <= q[j]) tmp[k++] = q[i++];
        else tmp[k++] = q[j++];
    }

    while (i <= mid) tmp[k++] = q[i++];
    while (j <= r) tmp[k++] = q[j++];

    for (i = l, j = 0; i <= r; ++i, ++j) q[i] = tmp[j];
}

这段代码可以分成三部分来看：

递归划分区间
合并两个有序区间
把合并结果写回原数组

下面逐段分析。

四、代码逐行解析

1. 递归终止条件

if (l >= r) return;

这里表示当前区间里只有一个元素，或者区间非法，那么就不需要继续排序了。

因为单个元素本身就是有序的。

2. 取中点并递归处理左右两边

int mid = l + r >> 1;
merge_sort(q, l, mid);
merge_sort(q, mid + 1, r);

这里先求出中点 mid，然后递归排序：

左半部分：[l, mid]
右半部分：[mid + 1, r]

注意：执行完这两句后，并不意味着整个区间 [l, r] 已经有序，只能说明：

左边有序了
右边有序了

接下来还差最后一步：合并

3. 定义三个指针

int k = 0, i = l, j = mid + 1;

这里三个变量的含义分别是：

i：指向左半部分当前比较的位置
j：指向右半部分当前比较的位置
k：指向辅助数组 tmp 当前要放元素的位置

其中：

左半区间是 [l, mid]
右半区间是 [mid + 1, r]

4. 比较两个有序区间，依次放入 tmp

while (i <= mid && j <= r) {
    if (q[i] <= q[j]) tmp[k++] = q[i++];
    else tmp[k++] = q[j++];
}

这是归并排序最核心的一步。

因为左右两部分都已经有序，所以只需要不断比较两边当前最小的元素，把更小的那个放进 tmp 中即可。

如果左边更小，就把 q[i] 放进去，然后 i++
如果右边更小，就把 q[j] 放进去，然后 j++

这样可以保证放进 tmp 的元素始终是从小到大的。

5. 处理剩余元素

while (i <= mid) tmp[k++] = q[i++];
while (j <= r) tmp[k++] = q[j++];

当上面的循环结束时，说明至少有一边已经取完了。

但另一边可能还有剩余元素，而由于那一边本身就是有序的，所以可以直接全部追加到 tmp 后面。

6. 写回原数组

for (i = l, j = 0; i <= r; ++i, ++j) q[i] = tmp[j];

这一步是把排好序的结果从辅助数组 tmp 拷贝回原数组 q 的当前区间 [l, r]。

这样，本轮递归对应的区间就真正完成排序了。

五、手动模拟一遍执行过程

以数组：

[3, 1, 2, 5, 4]

为例。

第一步：不断拆分

[3, 1, 2, 5, 4]
-> [3, 1, 2] 和 [5, 4]
-> [3, 1] 和 [2]，以及 [5] 和 [4]
-> [3] [1] [2] [5] [4]

拆到这里时，每个区间都只剩一个元素，递归开始返回。

第二步：开始合并

先合并 [3] 和 [1]

[3] + [1] -> [1, 3]

再把 [1, 3] 和 [2] 合并

[1, 3] + [2] -> [1, 2, 3]

再合并 [5] 和 [4]

[5] + [4] -> [4, 5]

最后合并左右两大块

[1, 2, 3] + [4, 5] -> [1, 2, 3, 4, 5]

整个数组就有序了。

六、时间复杂度和空间复杂度

1. 时间复杂度

归并排序的时间复杂度是：

O(n log n)

原因是：

每一层递归都会把数组分成两半，所以递归层数大约是 log n
每一层合并时，都需要把所有元素扫描一遍，所以每层工作量是 O(n)

因此总复杂度就是：

O(n log n)

而且归并排序的最好、最坏、平均时间复杂度都是 O(n log n)，这一点非常稳定。

2. 空间复杂度

归并排序需要额外的辅助数组 tmp 来存放合并结果，所以空间复杂度是：

O(n)

这也是它和快速排序相比的一个明显特点：归并排序更稳定，但更耗额外空间。

七、为什么归并排序是稳定排序

稳定排序的定义是：

如果两个元素相等，排序后它们的相对顺序不变，那么这种排序就是稳定的。

在这段代码里：

if (q[i] <= q[j]) tmp[k++] = q[i++];

注意这里用了 <=，而不是 <。

这意味着当 q[i] == q[j] 时，会优先把左边的元素放进 tmp。
由于左边元素原本在前，所以排序后它仍然在前，相对顺序没有被破坏。

因此，归并排序是稳定排序。

八、这段代码最容易写错的地方

1. 中点写法

int mid = l + r >> 1;

这在 C++ 中是可以工作的，因为加法优先级高于右移运算，相当于：

int mid = (l + r) >> 1;

不过为了可读性更强，很多人更喜欢写成：

int mid = (l + r) >> 1;

如果担心大整数溢出，也可以写成：

int mid = l + (r - l) / 2;

2. 区间边界

左半区间是：

[l, mid]

右半区间是：

[mid + 1, r]

所以比较时一定要写成：

i <= mid && j <= r

很多初学者会把边界写错成 <，导致最后一个元素漏掉。

3. 回写时下标不要混

for (i = l, j = 0; i <= r; ++i, ++j) q[i] = tmp[j];

这里：

i 对应原数组区间 [l, r]
j 对应辅助数组区间 [0, k - 1]

不要把 tmp 的下标也写成从 l 开始，否则就乱了。

4. `tmp` 数组要提前开好

这段代码默认 tmp 是一个全局辅助数组，比如：

const int N = 1e5 + 10;
int q[N], tmp[N];

如果没有提前定义好 tmp，代码是没法运行的。

九、归并排序的核心总结

归并排序最重要的不是背代码，而是理解这两个阶段：

1. 分

把一个大区间不断拆成左右两个小区间，直到每个区间只有一个元素。

2. 合

因为左右两边已经分别有序，所以可以用双指针把它们线性合并成一个更大的有序区间。

只要你真正理解了“先分后合”的过程，这段模板代码其实非常自然。

十、完整模板

最后给出一份更适合直接记忆的模板：

const int N = 1e5 + 10;
int q[N], tmp[N];

void merge_sort(int q[], int l, int r) {
    if (l >= r) return;

    int mid = (l + r) >> 1;

    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);

    int i = l, j = mid + 1, k = 0;

    while (i <= mid && j <= r) {
        if (q[i] <= q[j]) tmp[k++] = q[i++];
        else tmp[k++] = q[j++];
    }

    while (i <= mid) tmp[k++] = q[i++];
    while (j <= r) tmp[k++] = q[j++];

    for (i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
}