归并排序非递归实现详解：自底向上策略

边界问题处理

归并排序的逻辑基于完全二叉树结构，理想情况下每次都能完美均分。但现实中的数组长度往往不是 2 的整数次幂，这会带来边界越界风险。

常见越界情况

在迭代过程中，我们需要关注四个边界变量：begin1, end1（左区间起点终点）和 begin2, end2（右区间起点终点）。只有 begin1 是绝对安全的，其余三个都可能越界。

1. 右区间起点越界 (begin2 >= n)：说明当前左区间落单，没有对应的右区间可合并。此时直接跳过本次循环即可。
2. 右区间终点越界 (end2 >= n)：说明左右区间长度不等，右区间不足 gap 长度。此时需修正 end2 为 n - 1，确保只合并有效数据。

递归与非递归的差异

你可能会问：'为什么递归版本不需要这么多边界判断？'

• 递归（自顶向下）：拥有'自动适应'的灵活性。它只关心当前区间的实际长度，切分到长度为 1 自然停止。无论数组总长是多少，局部逻辑总是合法的。
• 非递归（自底向上）：带有'按规则执行'的僵硬性。它强制使用固定尺寸的'框'（gap）去框选相邻子数组。不管数组实际长度是否匹配，先按规则执行，再手动处理因'框太大'导致的边界溢出。这就是非递归版本必须显式判断 begin2 和 end2 的原因。

代码实现

下面是 C 语言的具体实现。注意内存分配、边界修正以及临时数组的使用。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 辅助函数：打印数组
void print_array(int* a, int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
}

// 归并排序非递归实现
void MergeSortNonR(int* a, int n) {
    // 申请临时数组用于归并
    int* tmp = (int*)malloc(sizeof(int) * n);
    if (tmp == NULL) {
        perror("malloc fail");
        return;
    }

    // 自底向上进行归并，初始 gap 为 1
    int gap = 1;
    while (gap < n) {
        // 每次合并两个长度为 gap 的子数组
        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;

            // 情况 1：右区间起点越界，说明左区间落单，无需归并
            if (begin2 >= n) break;

            // 情况 2：右区间终点越界，修正右区间终点
            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 *= 2;
    }

    free(tmp);
}

int main() {
    int arr[] = {10, 6, 7, 1, 3, 9, 4, 2};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("排序前：");
    print_array(arr, n);

    MergeSortNonR(arr, n);

    printf("排序后：");
    print_array(arr, n);

    return 0;
}

在实际工程中，非递归归并排序避免了递归调用的栈开销，适合对栈空间敏感的场景。但要注意，由于需要额外的 O(n) 空间存放临时数组，其空间复杂度并未降低。理解边界条件的处理逻辑，是掌握这一算法的关键。