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

为什么区间不能用 [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(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) 额外空间，但在现代计算机系统中，空间换时间的策略往往是值得的。其核心优势在于稳定可靠、性能不受数据分布影响，以及强大的外排序能力。在数据库系统、大数据处理等场景中，它发挥着不可替代的作用。