排序算法实战：归并排序的非递归实现

引言

非递归实现的归并排序通常被称为'自底向上'（Bottom-Up）版本。与递归版本不同，它不依赖系统栈进行拆分回溯，而是直接从长度为 1 的子数组开始，两两合并后步长翻倍，直到覆盖整个数组。

核心思路

将递归逻辑改写为循环结构是主要方法。虽然可以用栈模拟递归，但仅靠栈只能完成拆分，无法记录合并顺序——因为一旦子区间被弹出栈，原本需要合并的父区间信息就丢失了。因此，非递归版本的核心在于显式控制合并步长。

想象面前有一排乱序的扑克牌：

1. 步长为 1：相邻单张牌两两合并成有序对。
2. 步长为 2：相邻的有序对合并成有序四元组。
3. 重复此过程，步长每次翻倍，直到超过数组长度。

实现流程演示

以数组 [10, 6, 7, 1, 3, 9, 4, 2] 为例。

第一轮：gap = 1 相邻元素两两比较交换。例如 {10} 和 {6} 合并为 {6, 10}；{7} 和 {1} 合并为 {1, 7}。此时数组变为两两有序状态。

第二轮：gap = 2 将上一步生成的有序对再次合并。例如 {6, 10} 和 {1, 7} 合并为 {1, 6, 7, 10}。此时数组变为四四有序状态。

第三轮：gap = 4 继续合并，最终得到完全有序的数组。

边界处理难点

当数组长度不是 2 的整数次幂时，会出现'落单'情况。比如长度为 10，步长为 2 时，最后会剩下一个长度为 2 的子数组无法配对。

我们需要处理两种越界风险：

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

递归版本之所以不需要这么多判断，是因为它'顺势而为'，根据当前区间实际长度自动停止；而非递归版本必须按固定规则'框选'，所以遇到边界溢出时需要手动补漏。

代码实现

下面是完整的 C 语言实现，重点注意 gap 的倍增逻辑以及内存拷贝部分。

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

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

    
     gap = ;
     (gap < n) {
         ( i = ; i < n; i +=  * gap) {
            
             begin1 = i, end1 = i + gap - ;
            
             begin2 = i + gap, end2 = i + gap *  - ;

            
             (begin2 >= n) ;

            
             (end2 >= n) end2 = n - ;

            
             j = begin1;
             (begin1 <= end1 && begin2 <= end2) {
                 (a[begin1] <= a[begin2]) {
                    tmp[j++] = a[begin1];
                    begin1++;
                }  {
                    tmp[j++] = a[begin2];
                    begin2++;
                }
            }
            
             (begin1 <= end1) {
                tmp[j++] = a[begin1];
                begin1++;
            }
             (begin2 <= end2) {
                tmp[j++] = a[begin2];
                begin2++;
            }

            
            (a + i, tmp + i, () * (end2 - i + ));
        }
        
        gap *= ;
    }
    (tmp);
}