8. 递归与分治：归并排序的递归实现

分解-解决-合并三步走

归并排序，说白了就是「分而治之」思想的典型代表。我刚开始学排序算法时，总觉得冒泡、选择这些直观的算法就够了。直到有一次处理百万级的数据，冒泡排序跑了十几秒还没出结果……嗯，从那以后我才真正重视起归并排序这种 O(n log n) 的算法。

归并排序的核心思想其实很简单，就三个字：分、治、合。你想想看，如果给你一副乱序的扑克牌，你会怎么排？我个人的习惯是先分成两半，每半排好，再合并到一起。归并排序就是这个思路。

算法流程

归并排序的递归实现，严格遵循三步走：

1. 分解：把数组从中间切成两半，递归地对左右两半做同样的事
2. 解决：当子数组只剩一个元素时，它天然就是有序的（递归终止条件）
3. 合并：把两个有序的子数组合并成一个有序的数组

这里有个关键点——合并这一步才是真正的「干活」的地方。分解和解决只是把问题变小，真正排序的动作发生在合并时。

代码实现

下面是我写的一个标准实现。注意看递归的终止条件和合并的逻辑：

#include <stdio.h>
#include <stdlib.h>

// 合并两个有序子数组
void merge(int arr[], int left, int mid, int right) {
    int i, j, k;
    int n1 = mid - left + 1;
    int n2 = right - mid;

    // 创建临时数组
    int *L = (int*)malloc(n1 * sizeof(int));
    int *R = (int*)malloc(n2 * sizeof(int));

    // 拷贝数据到临时数组
    for (i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    // 合并两个有序数组
    i = 0; j = 0; 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++;
    }

    free(L);
    free(R);
}

// 递归实现归并排序
void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 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);

    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    return 0;
}

递归过程可视化

为了让你更直观地理解递归的调用过程，我画了一张图。这张图展示了对一个长度为 7 的数组进行归并排序时，递归是如何一层层分解，再一层层合并的：

避坑指南

分治思想的核心

归并排序教会我们一个道理：复杂问题可以拆成简单问题。你想想看，排序一个数组很难，但排序一个元素很简单（什么都不用做），合并两个有序数组也很简单。这就是分治的魅力。

我个人习惯在写递归函数时，先想清楚三件事：

1. 终止条件是什么？—— 对于归并排序，就是 left >= right
2. 如何分解问题？—— 找到中间点，分成两半
3. 如何合并结果？—— 把两个有序数组合并

只要这三件事想清楚了，代码写起来就顺了。

复杂度分析

指标	值	说明
时间复杂度	O(n log n)	最好、最坏、平均都是这个值，很稳定
空间复杂度	O(n)	需要额外的临时数组来合并
稳定性	稳定	相等元素的相对顺序不会改变
递归深度	log₂n	对于 n=100万，深度约 20 层

归并排序的稳定性在实际项目中很有用。比如你要先按时间排序，再按优先级排序，稳定的排序算法能保证第一次排序的结果不被破坏。

好了，归并排序的递归实现就讲到这里。记住「分解-解决-合并」这三步，你就能写出自己的归并排序了。