归并排序详解：分治策略与 C 语言实战

归并排序：分治思想的完美演绎

基本思想

归并排序（Merge Sort）是分治法（Divide and Conquer）的经典应用，由计算机科学先驱约翰·冯·诺依曼于 1945 年提出。核心逻辑很简单：将大问题拆解为小问题，解决后再合并结果。

算法流程主要包含两个阶段：

1. 分（Divide）：递归地将当前数组分割成两个子数组，直到每个子数组只包含一个元素（此时天然有序）。
2. 治（Conquer）：将两个有序子数组合并成一个新的有序数组。

归并的核心操作是合并两个有序数组：每次比较两个数组的首元素，将较小者放入新数组，直到所有元素合并完成。

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

// 递归辅助函数
void _MergeSort(int* a, int* tmp, int begin, int end) {
    // 递归终止条件：当子数组只有一个元素时
    if (begin == end) {
        return;
    }

    // 计算中间点
    int mid = (begin + end) / 2;
    
    // 注意区间划分：[begin, mid] 和 [mid+1, end]
    // 如果分为 [begin, mid-1] 和 [mid, end] 会有坑，比如数据 2 3 6 7
    _MergeSort(a, tmp, begin, mid);
    _MergeSort(a, tmp, mid + 1, end);

    // 归并两个有序区间
    int begin1 = begin, end1 = mid;
    int begin2 = mid + 1, end2 = end;
    int i = begin;

    while (begin1 <= end1 && begin2 <= end2) {
        if (a[begin1] < a[begin2]) {
            tmp[i++] = a[begin1++];
        } else {
            tmp[i++] = a[begin2++];
        }
    }

    // 处理剩余元素
    while (begin1 <= end1) {
        tmp[i++] = a[begin1++];
    }
    while (begin2 <= end2) {
        tmp[i++] = a[begin2++];
    }

    // 将合并结果复制回原数组
    memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}

// 归并排序入口函数
void MergeSort(int* a, int n) {
    int* tmp = (int*)malloc(sizeof(int) * n);
    if (tmp == NULL) {
        perror("malloc fail");
        return;
    }

    _MergeSort(a, tmp, 0, n - 1);
    free(tmp);
    tmp = NULL;
}

// 测试案例
int main() {
    int a[] = {2, 3, 5, 4, 7, 1};
    MergeSort(a, 6);
    for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++) {
        printf("%d ", a[i]);
    }
    return 0;
}

为什么区间不能用 [begin, mid-1] 和 [mid, end]？

这是一个常见的实现陷阱。假设 10 个数据，下标从 0 到 9，mid 为 4。 如果是 [begin, mid-1] 即 [0, 3] 和 [mid, end] 即 [4, 9]。 在 [0, 3] 区间里，mid-1 会变成 0，分成 [0, 0] 和 [1, 3]。 而在 [1, 3] 中，mid-1 变成 1，分成 [1, 1] 和 [2, 3]。 到了 [2, 3]，mid-1 依然是 1，导致分成 [2, 1] 和 [1, 3]，出现死循环或逻辑错误。

操作	时间复杂度	说明
分解数组	O(log n)	递归深度
合并子数组	O(n)	每层需要遍历所有元素
总复杂度	O(n log n)	稳定的高效率排序

空间复杂度

归并排序需要 O(n) 的额外空间：

• 用于存储合并过程中的临时数组
• 递归调用栈空间 O(log n)，通常临时数组占主导

非递归归并实现

非递归版本可以理解为自底向上的归并：先 1+1 归并，再 2+2 归并，以此类推。

void MergeSortNonR(int* a, int n) {
    int* tmp = (int*)malloc(sizeof(int) * n);
    if (tmp == NULL) {
        perror("malloc fail");
        return;
    }

    int gap = 1;
    for (int i = 0; i < n; i += 2 * gap) {
        int begin1 = i, end1 = i + gap - 1;
        int begin2 = i + gap, end2 = i + 2 * gap - 1;

        // 第二组完全越界，跳过本次合并
        if (begin2 >= n) {
            break;
        }

        // 第二组部分越界，修正边界
        if (end2 >= n) {
            end2 = n - 1;
        }

        int j = i;
        while (begin1 <= end1 && begin2 <= end2) {
            if (a[begin1] < a[begin2]) {
                tmp[j++] = a[begin1++];
            } else {
                tmp[j++] = a[begin2++];
            }
        }

        while (begin1 <= end1) {
            tmp[j++] = a[begin1++];
        }
        while (begin2 <= end2) {
            tmp[j++] = a[begin2++];
        }

        memcpy(a + i, tmp + i, (end2 - i + 1) * sizeof(int));
    }
    free(tmp);
    tmp = NULL;
}

如果数据量不是 2 的幂次方，就会出现溢出或越界。把归并区间打印出来分析，主要有两种情况：

1. begin2 直接溢出，无需归并。
2. begin2 未溢出，但 end2 溢出，需修正 end2 为 n-1。

非递归实现要点：

• gap 参数：控制当前归并的子数组大小，从 1 开始，每次迭代翻倍。
• 边界处理：关键步骤，处理数组大小不是 2 的幂的情况。
• 迭代过程：第 1 轮 1+1 归并，第 2 轮 2+2 归并，第 k 轮 2^k 归并。

归并排序特性总结

1. 稳定排序：

   • 当两个元素相等时，优先选择左子数组的元素。
   • 保持相等元素的原始相对位置不变。
   • 适用于多关键字排序等对稳定性有要求的场景。

2. 时间复杂度：

   • 最优、平均、最差均为 O(n log n)。
   • 不受输入数据影响，性能非常稳定。

3. 空间复杂度：

   • O(n) 额外空间。
   • 递归实现还有 O(log n) 的栈空间开销。

4. 外排序优势：

   • 归并排序是少数能高效处理外部存储（如硬盘）数据的排序算法。
   • 适合处理超过内存容量的海量数据。
   • 工作流程：大文件分割 -> 内存排序小块 -> 合并已排序小块。

结语

归并排序是分治思想的典型体现，通过'分而治之'的策略达到 O(n log n) 的高效排序。尽管需要 O(n) 额外空间，但在现代计算机系统中，空间换时间的策略往往是值得的。其核心优势在于稳定可靠、性能不受数据分布影响，以及强大的外排序能力。在数据库系统、大数据处理等场景中，它发挥着不可替代的作用。