归并排序非递归实现详解

解决方案

• 解决 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;
    }

    // 自底向上进行归并，初始时 gap 为 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...
        gap *= 2;
    }

    free(tmp);
}

这段代码展示了如何通过控制 gap 和边界变量来实现自底向上的归并。在实际工程中，如果追求极致性能，还可以考虑减少内存拷贝次数，比如通过双缓冲区交替归并来优化空间访问模式。