归并排序非递归实现详解

• 归并：左 [1, 6, 7, 10]，右 [2, 3, 4, 9]。最终得到完全有序数组 [1, 2, 3, 4, 6, 7, 9, 10]。

边界处理疑难点

1. 均分情况

当数组长度恰好是 2 的幂次（如 8），每一步都能完美凑齐左右半边，逻辑简单。

2. 不均分情况

现实中的数组长度往往不是 2 的整数次幂（如 10）。此时会出现'落单'或'越界'问题。

例如 gap=2 时，10 个元素分为 2+2+2+2+2，最后一个 2 没有配对对象；gap=4 时，分为 4+4+2，最后的 2 也是落单。

我们需要关注四个边界：begin1, end1, begin2, end2。其中只有 begin1 天然安全，其余三个都可能越界。

解决方案：

1. 左数组落单：若 begin2 >= n，说明右半区间不存在，直接跳过本次循环。
2. 右数组越界：若 end2 >= n，说明右半区间存在但长度不足，需将 end2 修正为 n - 1。

3. 递归与非递归的区别

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

• 递归（自顶向下）：拥有自动适应的灵活性。它只关心'当前区间切两半'，直到长度为 1 自然终止。边界会随递归深度自然收敛。
• 非递归（自底向上）：带有按规则执行的僵硬性。它严格遵循 1→2→4→8 的翻倍逻辑，必须手动处理因'框太大'导致的边界溢出问题。

代码实现

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

    // 自底向上，初始步长为 1
    int gap = 1;
    while (gap < n) {
        for (int i = 0; i < n; i += 2 * gap) {
            // 定义左右子数组的边界
            int begin1 = i, end1 = i + gap - 1;
            int begin2 = i + gap, end2 = i + gap * 2 - 1;

            // 如果右子数组起点已越界，说明左子数组落单，无需归并
            if (begin2 >= n) break;

            // 如果右子数组终点越界，修正为数组末尾
            if (end2 >= n) end2 = n - 1;

            // 归并到临时数组
            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);
}

这段代码通过 begin2 和 end2 的判断，优雅地解决了任意长度数组的归并问题。实际运行时，注意内存分配失败的处理以及 memcpy 的范围计算，确保不会发生缓冲区溢出。