归并排序非递归实现详解

第一轮结束，数组变成了两两有序。

第二轮：gap=2

此时将相邻的 2 个有序子数组合并。

1. 第一次归并：左 [0,1] => {6,10}，右 [2,3] => {1,7}。
   • 比较 6 和 1 -> 取 1
   • 比较 6 和 7 -> 取 6
   • 比较 10 和 7 -> 取 7
   • 剩下 10 -> 取 10 结果：[1, 6, 7, 10, 3, 9, 2, 4]
2. 第二次归并：左 [4,5] => {3,9}，右 [6,7] => {2,4}。
   • 比较 3 和 2 -> 取 2
   • 比较 3 和 4 -> 取 3
   • 比较 9 和 4 -> 取 4
   • 剩下 9 -> 取 9 结果：[1, 6, 7, 10, 2, 3, 4, 9]

第二轮结束，数组变成了四四有序。

第三轮：gap=4

最后一步，将两个长度为 4 的有序数组合并。

• 左 [0,3] => {1, 6, 7, 10}，右 [4,7] => {2, 3, 4, 9}。
• 依次比较并填入临时数组，最终得到完全有序的结果：[1, 2, 3, 4, 6, 7, 9, 10]

边界处理：当数组长度不是 2 的幂时

归并排序的逻辑结构基于'完全二叉树'，理想情况下每一步都能完美左右均分。但现实中的数组长度往往不是 2 的整数次幂，这就带来了边界问题。

不均分引起的问题

当 gap 倍增时，可能会出现以下情况：

1. 左数组落单：begin2 >= n。即当前左子数组后面没有足够的右子数组与之配对。
2. 右数组越界：end2 >= n。即右子数组的终点超出了数组实际长度。

解决方案

我们需要针对这两种情况进行判断：

1. 若 begin2 越界：说明当前左子数组落单，没有右子数组可合并，直接跳过本次循环即可。
2. 若仅 end2 越界：说明左右数组进行的是不对等长度的归并。此时需修正右数组的终点 end2，将其限制在 n - 1。

递归与非递归的区别

你可能会疑惑：'为什么递归版本的归并排序，好像没有这么多复杂的边界判断？'

答案的核心在于两者的逻辑差异：

• 递归（自顶向下）：拥有'自动适应'的灵活性。它不预设任何拆分规则，只遵循'把当前数组切两半'的逻辑，直到子数组长度为 1。它不关心整体数组长度是多少，只聚焦当前手里的区间有几个元素，边界会自然收敛。
• 非递归（自底向上）：带有'按规则执行'的僵硬性。它从最小步长开始，严格遵循 1→2→4→8 的翻倍逻辑，用固定尺寸的'框'去框选相邻子数组。这种'刻舟求剑'式的逻辑，不管数组实际长度是否匹配，先按规则执行，再处理因'框太大'导致的边界溢出问题。

代码实现

下面是完整的 C 语言实现，包含了必要的内存分配、边界检查以及归并逻辑。

void MergeSortNonR(int* a, int n) {
    // 申请一个临时数组用于归并
    int* tmp = (int*)malloc(sizeof(int) * n);
    if (tmp == NULL) {
        perror("malloc fail\n");
        return;
    }

    // 自底向上进行归并，初始时进行 "1 1" 归并
    int gap = 1;
    while (gap < n) {
        for (int i = 0; i < n; i += 2 * gap) {
            // begin1 : 左半区间数组的起点
            // end1：左半区间数组的终点
            int begin1 = i, end1 = i + gap - 1;
            
            // begin2：右半区数组的起点
            // end2：右半区间数组的终点
            int begin2 = i + gap, end2 = i + gap * 2 - 1;

            // 出现数组落单不需要进行归并
            if (begin2 >= n) break;

            // 出现不对等长度匹配，修正 end2
            if (end2 >= n) end2 = n - 1;

            // 归并到 tmp 数组的起始位置
            int j = begin1;
            
            // 进行一组归并
            while (begin1 <= end1 && begin2 <= end2) {
                if (a[begin1] <= a[begin2]) {
                    tmp[j++] = a[begin1];
                    begin1++;
                } else {
                    tmp[j++] = a[begin2];
                    begin2++;
                }
            }

            // 处理未归并完的左子数组
            while (begin1 <= end1) {
                tmp[j++] = a[begin1];
                begin1++;
            }

            // 处理未归并的右子数组
            while (begin2 <= end2) {
                tmp[j++] = a[begin2];
                begin2++;
            }

            // 归并一组拷贝一组回原数组
            memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
        }
        
        // gap 变化为：1->2->4->8->16...
        // "1 1" 归并 "2 2" 归并 "4 4" 归并 ...
        gap *= 2;
    }

    free(tmp);
}

通过上述方式，我们避免了递归带来的栈开销，同时通过精细的边界控制，保证了算法在非 2 的幂次数组上的正确性。