归并排序非递归实现：自底向上的核心逻辑与代码解析

前言

非递归实现的归并排序通常被称为'自底向上'（Bottom-Up）策略。与递归版本先将数组对半拆分直到只剩一个元素再回溯合并不同，非递归版本直接从最小的子数组（长度为 1）开始，两两合并，然后步长翻倍（2, 4, 8...），直到整个数组有序。

核心思路

将递归转换为非递归主要有两种路径：用栈模拟递归过程，或者直接改写为循环结构。但在归并排序中，单纯用栈模拟往往只能做到拆分，难以在弹出时准确找回合并指令。因为一旦区间被拆分压栈，原区间的合并上下文就丢失了，程序不知道这两个子区间原本是'兄弟'关系。

因此，我们采用循环结构。核心在于控制步长（gap）：

1. 初始 gap = 1，将数组视为 N 个长度为 1 的有序子数组。
2. 相邻两个长度为 1 的子数组合并成长度为 2 的有序子数组。
3. gap 翻倍为 2，继续合并成长度为 4 的有序子数组。
4. 重复此过程，直到 gap 超过数组长度。

想象面前有一排乱序的扑克牌，先两两整理成有序的 2 张一组，再把这些组两两整理成 4 张一组，以此类推，直到整副牌有序。

实现流程演示

假设数组为 [10, 6, 7, 1, 3, 9, 4, 2]，我们可以观察循环如何控制归并过程。

第一轮：gap = 1

此时每 1 个元素为一组进行两两合并。

• [10] 和 [6] 合并 -> [6, 10]
• [7] 和 [1] 合并 -> [1, 7]
• [3] 和 [9] 合并 -> [3, 9]
• [4] 和 [2] 合并 -> [2, 4]

数组变为两两有序：[6, 10, 1, 7, 3, 9, 2, 4]。

第二轮：gap = 2

此时每 2 个元素为一组进行合并。

• [6, 10] 和 [1, 7] 合并 -> [1, 6, 7, 10]
• [3, 9] 和 [2, 4] 合并 -> [2, 3, 4, 9]

数组变为四四有序：[1, 6, 7, 10, 2, 3, 4, 9]。

第三轮：gap = 4

最后将左右两部分合并。

• [1, 6, 7, 10] 和 [2, 3, 4, 9] 合并 -> [1, 2, 3, 4, 6, 7, 9, 10]

至此，数组完全有序。

边界问题的处理

归并排序的逻辑基于'完全二叉树'，理想情况下每一步都能完美均分。但当数组长度不是 2 的整数次幂时，会出现边界问题。

例如长度为 10 的数组，在 gap = 2 时，最后会剩下一个长度为 2 的子数组无法配对；gap = 4 时，最后剩下长度为 2 的部分。这些落单的元素或不对等的区间需要特殊处理。

主要涉及四个边界变量：begin1, end1（左区间起点终点）和 begin2, end2（右区间起点终点）。其中只有 begin1 是绝对安全的，其余三个都可能越界。

解决方案分为两种情况：

1. 数组落单：如果 begin2 >= n，说明当前左子数组后面没有对应的右子数组了，直接跳过本次循环，无需归并。
2. 长度不等：如果 end2 >= n，说明右区间超出了数组范围，需要将 end2 修正为 n - 1，确保只合并有效部分。

递归与非递归的区别

你可能会疑惑，为什么递归版本不需要这么多复杂的边界判断？

关键在于递归是'顺势而为'。它不预设拆分规则，只遵循'切两半'的逻辑，直到子数组长度为 1 自然终止。它只关心当前手里的区间有几个元素，边界会自然收敛。

而非递归是'刻舟求剑'。它按固定规则（1→2→4→8）执行，不管数组实际长度是否匹配，先按规则框选，再处理因'框太大'导致的边界溢出。这种僵硬性正是非递归版本需要额外边界判断的核心原因。

代码实现

下面是完整的 C 语言实现。注意内存分配和边界修正的细节。

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

void MergeSortNonR(int* a, int n) {
    // 申请临时数组用于归并
    int* tmp = (int*)malloc(sizeof(int) * n);
    if (tmp == NULL) {
        perror("malloc failed");
        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;

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

            // 情况 2：右区间终点越界，修正为数组末尾
            if (end2 >= n) end2 = n - 1;

            // 归并到临时数组
            int j = begin1;
            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, sizeof(int) * (end2 - i + 1));
        }
        // 步长翻倍
        gap *= 2;
    }
    free(tmp);
}

这段代码通过双重循环实现了自底向上的归并。外层循环控制步长增长，内层循环处理当前步长下的所有区间对。重点在于 if (begin2 >= n) break; 和 if (end2 >= n) end2 = n - 1; 这两处边界保护，它们确保了算法在任何长度的数组上都能安全运行。