归并排序非递归实现详解

前言

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

核心思路：为什么不用栈模拟？

将递归转换为非递归主要有两种路径：用栈结构模拟递归过程，或者直接将逻辑改写为循环。但在归并排序中，单纯用栈模拟往往行不通。

假设我们要排序数组 arr = [8, 4, 5, 7]，下标是 0 到 3。

初始状态：栈中有任务 [0, 3]。 第一步：弹出 [0, 3]。计算 mid = 1。拆分为左 [0, 1] 和右 [2, 3]。将这两个区间压入栈。 关键点： [0, 3] 被彻底扔了，没人记得原本是要合并这俩段。 后续步骤同理，[0, 1] 也会被拆解成单元素后丢弃。

问题出现了： 当 [0, 0] 和 [1, 1] 都处理完了，按理说应该执行 merge(0, 0, 1) 把它们变成 [4, 8]。但是！栈里没有这个指令，之前的父区间早就被丢弃了，程序不知道这两个单元素数组是'兄弟'关系。

因此，我们采用循环结构。递归是'先拆分，后合并'，而非递归则是直接从最小单元开始'只合并'。

算法流程

1. 步长（gap）设为 1：将数组看作由 N 个长度为 1 的有序子数组组成。
2. 两两合并：相邻的两个长度为 1 的子数组合并成长度为 2 的有序子数组。
3. 步长翻倍：将步长设为 2，相邻的两个长度为 2 的子数组合并成长度为 4。
4. 重复：步长继续翻倍（4, 8, 16...），直到步长超过数组长度。

简单理解：想象面前有一排乱序的扑克牌。先把相邻的每 1 张牌看作一组，两两合并成有序的 2 张牌；再把相邻的每 2 张牌看作一组，两两合并成有序的 4 张牌……直到步长超过数组长度，排序完成。

实现细节演示

假设存在如下数组 [10, 6, 7, 1, 3, 9, 4, 2]，我们来看看循环结构是如何控制归并过程的。

核心变量

• gap: 当前子序列的长度
• 左数组区间: [begin1, end1]
• 右数组区间: [begin2, end2]

第一轮：gap=1

此时我们将数组视为 8 个长度为 1 的子数组。

1. 第一次合并：左 [0,0] => {10}，右 [1,1] => {6}。6 小于 10，交换位置。结果：[6, 10, 7, 1, 3, 9, 4, 2]
2. 第二次合并：左 [2,2] => {7}，右 [3,3] => {1}。1 小于 7，交换位置。结果：[6, 10, 1, 7, 3, 9, 4, 2]
3. 第三次合并：左 [4,4] => {3}，右 [5,5] => {9}。3 小于 9，无需变动。结果不变。
4. 第四次合并：左 [6,6] => {4}，右 [7,7] => {2}。2 小于 4，交换位置。结果：[6, 10, 1, 7, 3, 9, 2, 4]

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

第二轮：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 的幂次数组上的正确性。