归并排序非递归实现详解

相比之下，递归版本（自顶向下）拥有自动适应的灵活性，它只关注当前区间的实际长度，自然收敛到基本情况。而非递归版本（自底向上）规则固定，必须手动补漏，这也是其代码中边界判断较多的原因。

代码实现

以下是 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 fail");
        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;

            // 归并到 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);
}

这段代码通过 memcpy 将临时数组的数据回写，保证了空间效率。在实际工程中，若对稳定性有要求且内存允许，这种原地归并的变体也是常见的选择。