数据结构：归并排序与分治思想详解

为什么区间划分要注意？

在递归拆分时，我们通常使用 [begin, mid] 和 [mid+1, end]。如果错误地写成 [begin, mid-1] 和 [mid, end]，在某些情况下会导致死循环。

假设数组有 10 个数据，下标从 0 到 9。如果取 mid = 4，按错误写法分成 [0, 3] 和 [4, 9]。在 [0, 3] 中 mid-1=1，分成 [0, 1] 和 [2, 3]。看似没问题，但在某些边界条件下，比如 [2, 3] 再次拆分时，若 mid 计算导致区间重叠或无法收敛，就会出问题。最稳妥的方式始终是让中间点归属左半部分，右半部分从 mid+1 开始。

空间复杂度

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

    // gap 是当前归并子数组的大小，从 1 开始，每次翻倍
    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;
}

非递归实现要点

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 归并 → 子数组大小为 2^k

每一层的时间复杂度都是 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) 的额外空间，但在现代计算机系统中，这种空间换时间的策略往往是值得的。

它的核心优势在于稳定可靠、性能不受数据分布影响，以及强大的外排序能力。这使得它在数据库系统、大数据处理等场景中发挥着不可替代的作用，是每个程序员必须掌握的经典算法之一。