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

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

假设我们有 10 个数据，下标从 0 到 9。如果采用 [begin, mid-1] 和 [mid, end] 的划分方式：

此时 mid = 4，分成 [0, 3] 和 [4, 9]。看似没问题，但在递归深入后会出现问题。

在 [0, 3] 区间里，mid = 1，mid-1 = 0。于是分成 [0, 0] 和 [1, 3]。 [0, 0] 满足终止条件跳出。 但在 [1, 3] 区间里，mid = 2，mid-1 = 1。于是分成 [1, 1] 和 [2, 3]。 到了 [2, 3] 区间，mid = 2，mid-1 = 1。这时左区间变成 [2, 1]，右区间是 [2, 3]。 左区间起始大于结束，逻辑上显然不对，这会导致递归无法正确收敛。

所以标准的写法必须是 [begin, mid] 和 [mid+1, end]。

空间复杂度

归并排序需要 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;
    }

    // gap 是每次归并数据的长度
    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;
        }

        // 第二组的 begin2 没越界，end2 越界了，需要修正边界
        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;
}

如果数组长度为 10，就会出现边界溢出的情况。通过打印归并区间分析，主要有两种边界情况：

1. begin2 溢出：说明没有第二个子数组了，直接结束。
2. begin2 不溢出，但 end2 溢出：说明第二个子数组不完整，需要修正 end2 为 n-1。

非递归实现要点：

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

时间复杂度同样是 O(n log n)，因为每一层都是 O(n)，一共 log n 层。空间复杂度也是 O(n)。

归并排序特性总结

1. 稳定排序：

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

2. 时间复杂度：

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

3. 空间复杂度：

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

4. 外排序优势：

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

结语

归并排序是分治思想的完美体现，通过'分而治之'的策略达到 O(n log n) 的高效排序。尽管它需要 O(n) 的额外空间，但在现代计算机系统中，用空间换时间的策略往往是值得的。

其核心优势在于性能稳定、支持外部排序以及天然的并行潜力。在数据库系统、大数据处理等场景中，归并排序发挥着不可替代的作用，是每个程序员必须掌握的经典算法之一。