数据结构：归并排序的分治实现与特性分析

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

这是一个常见的边界陷阱。假设数组有 10 个数据，下标从 0 到 9。

如果使用 [begin, mid-1] 和 [mid, end]： 此时 mid 为 4，则分成 [0, 3] 和 [4, 9]。 在 [0, 3] 区间里，mid 为 1，若按公式变成 [0, 0] 和 [1, 3]。 但在 [2, 3] 区间里，mid 为 2，若按公式变成 [2, 1] 和 [2, 3]，左区间右边界小于左边界，导致死循环或越界。

因此，标准的分治写法应保证 mid 属于左区间，即 [begin, mid] 和 [mid+1, end]。

空间复杂度

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

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

非递归归并实现

非递归版本通过迭代的方式模拟递归过程，避免了递归调用的栈开销。

核心思路是控制归并的步长 gap。初始 gap 为 1，表示先进行 1 对 1 的归并；下一轮 gap 翻倍，进行 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;
}

非递归实现要点

1. gap 参数：控制当前归并的子数组大小，从 1 开始，每次迭代翻倍。
2. 边界处理：关键步骤，处理数组大小不是 2 的幂的情况。
   • 当第二个子数组完全越界（begin2 >= n），跳过本次合并。
   • 当第二个子数组部分越界（end2 >= n），修正其边界为 n-1。
3. 迭代过程：
   • 第 1 轮：1 对 1 归并 → 每个子数组大小为 1
   • 第 2 轮：2 对 2 归并 → 子数组大小为 2
   • 第 k 轮：2^k 归并 → 子数组大小为 2^k

归并排序特性总结

1. 稳定排序：

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

2. 时间复杂度：

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

3. 空间复杂度：

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

4. 外排序优势：

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

尽管需要 O(n) 额外空间，但在现代计算机系统中，空间换时间的策略往往是值得的。归并排序在数据库系统、大数据处理、外部排序等场景中发挥着不可替代的作用，是每个程序员必须掌握的经典算法之一。