排序算法指南：归并排序(非递归)

Ne0inhk

22 Mar 2026 — 18 min read

前言：

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

一、归并排序非递归的核心思路

递归算法转换为非递归实现主要有两种常见方法：

1.使用栈结构模拟递归过程

2.将递归逻辑改写为循环结构

1.1 栈模拟失效

如果仅通过栈结构模拟递归过程，我们只能够做到拆分数组，而不能做到合并数组。

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



初始状态：栈中有任务 [0, 3]。





第一步：弹出 [0, 3]。



①计算 mid = 1。



②拆分为左 [0, 1] 和右 [2, 3]。



③将 [2, 3] 和 [0, 1] 压入栈。



④关键点：[0, 3] 被彻底扔了，没人记得原本是要合并这俩段。





第二步：弹出 [0, 1]。



①计算 mid = 0。



②拆分为 [0, 0] 和 [1, 1]。



③将 [1, 1] 和 [0, 0] 压入栈。



④关键点：[0, 1] 也被扔了。





第三步：弹出 [0, 0]。



①区间长度为 1，是基本情况（Base Case），不需要做任何事。



②直接结束本次循环。





第四步：弹出 [1, 1]，同上，直接结束。



问题出现了：此时 [0, 0] 和 [1, 1] 都处理完了。按理说，现在应该执行 merge(0, 0, 1) 把它们变成 [4, 8]。

                     但是！栈里没有这个指令，之前的 [0, 1] 早就被丢弃了，程序不知道这两个 1 长度的数组是“兄弟”关系。



后续：栈里剩下的 [2, 3] 也会经历同样的命运，被拆解成单元素后被遗忘。

1.2 循环结构实现

递归版本是“先拆分，后合并”，而非递归版本则是直接从最小的子数组开始“只合并”，不需要拆分。

核心原理如下：



①步长（gap）设为 1：首先将数组看作由 N 个长度为 1 的有序子数组组成。



②两两合并：相邻的两个长度为 1 的子数组合并成长度为 2 的有序子数组。



③步长翻倍：将步长设为 2，相邻的两个长度为 2 的子数组合并成长度为 4 的有序子数组。



④重复：步长继续翻倍（4, 8, 16...），直到步长超过数组长度，此时整个数组就有序了

简单理解：想象面前有一排乱序的扑克牌



①步长=1：先把相邻的每1张牌看作一组，两两合并成有序的 2张牌。



②步长=2：再把相邻的每2张牌看作一组，两两合并成有序的 4张牌。



③步长=4：继续合并为 8张……



④循环：直到步长超过数组长度，排序完成

二、归并排序非递归的实现流程

假设存在如下数组 [10, 6, 7, 1, 3, 9, 4, 2],一步一步演示循环结构是如何控制归并过程。

2.1核心变量回顾：

gap: 当前子序列的长度



左数组区间：[begin1 , end1]



begin1 :左半区间数组的起点 end1：左半区间数组的终点



右数组区间：[begin2,end2]


begin2：右半区数组的起点 end2 ：右半区间数组的终点

2.2核心流程展示

第一轮:gap=1



1.第一次合并



左子数组：[0,0] => {10} 右子数组：[1,1] => {6}



begin1=0 end1=0 begin2=1 end2=1



即 [10] 和 [6] 操作： 6 小于 10，交换位置。



结果： [6, 10, 7, 1, 3, 9, 4, 2]





2.第二次合并



左子数组：[2,2] => {7} 右子数组: [3,3] => {1}



begin1=2 end1=2 begin2=3 end2=3



即 [7] 和 [1] 操作： 1 小于 7，交换位置。



结果： [6, 10, 1, 7, 3, 9, 4, 2]





3.第三次合并



左子数组：[4,4] => {3} 右子数组: [5,5] => {9}



begin1=4 end1=4 begin2=5 end2=5



即 [3] 和 [9] 操作： 3 小于 9，无需变动（本来就有序）。



结果： [6, 10, 1, 7, 3, 9, 4, 2]





4.第四次合并



左子数组：[6,6] => {4} 右子数组: [7,7] => {2}



begin1=6 end1=6 begin2=7 end2=7



即 [4] 和 [2] 操作： 2 小于 4，交换位置。



第一轮结束，此时数组变成了两两有序：[6, 10, 1, 7, 3, 9, 2, 4]

第二轮:gap=2



1.第一次归并



左子数组：[0,1] => {6,10} 右子数组: [2,3] => {1,7}



begin1=0 end1=1 begin2=2 end2=3



归并过程:

                比较 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]



第二轮结束，此时数组变成了四四有序：[1, 6, 7, 10, 2, 3, 4, 9]

第三轮:gap= 4



1.第一次归并



左子数组：[0,3] => {1, 6, 7, 10} 右子数组：[4,7] => {2, 3, 4, 9}



begin1=0 end1=3 begin2=4 end2=7



归并过程：
                1 vs 2 -> 取 1
                6 vs 2 -> 取 2
                6 vs 3 -> 取 3
                6 vs 4 -> 取 4
                6 vs 9 -> 取 6
                7 vs 9 -> 取 7
                10 vs 9 -> 取 9
                剩下 10 -> 取 10



结果： [1, 2, 3, 4, 6, 7, 9, 10]



第三轮结束，数组完全有序 [1, 2, 3, 4, 6, 7, 9, 10]

三、归并排序非递归的疑难点

3.1满足左右数组均分

归并排序的逻辑结构是基于“完全二叉树”，当满足每一步都能凑齐完美的“左半边”和“右半边”

步长 1：8=1+1+1+1+1+1+1+1（完美）



步长 2：8=2+2+2+2（完美）



步长 4：8=4+4（完美）



步长 8：8=8（完美）

如下图示：假设存在一个数组 [10 6 7 1 3 9 4 2]

3.2不满足左右数组均分

这个问题的根本原因在于：归并排序的逻辑结构是基于“完全二叉树”的（总是 1→2→4→8），而现实中的数组长度往往不是 2 的整数次幂，因为 2^k的倍增网格无法完美覆盖任意整数 N，多出来的部分就是所谓的“边界问题”。

步长 1：10= 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1（完美，因为 10 是偶数）



步长 2：10 = 2 + 2 + 2 + 2 + 2 (最后一个数组落单)



步长 4：10 = 4 + 4 + 2 (最后一个数组落单)



步长 8：10 = 8 + 2 (最后一个数组落单)

如下图示：假设存在一个数组[6 1 2 7 9 3 4 5 10 8]

3.2.1 不均分引起的问题

我们注意到：如下四个边界中，只有左半区间数组的起点能够满足严格在数组下标的索引中，其余边界均有可能有越界的风险，所以我们要控制边界问题



begin1 :左半区间数组的起点 end1：左半区间数组的终点


begin2：右半区数组的起点    end2 ：右半区间数组的终点

3.2.2 解决方案

我们可以将该问题其分为两组进行讨论：



问题1. （情况二、情况三）当begin2出现越界时（begin2 >= n），即当前左子数组出现落单，如下图所示的左数组元素为：{8，10}



问题2. （情况一）当仅有end2出现越界时 (end2 >= n) ,即当前出现的是长度不对等进行归并，如下图所示：{1，2，3，4，5，6，7，9} 与 {8，10}



解决1：若当begin2出现越界时，即出现数组落单，不需要对其进行归并排序，我们可以直接跳过



解决2：当仅有end2出现越界时，即当前左数组和右数组进行的是不对等长度归并，我们需要进行修正右数组，将end2修正为 n-1 即可。

3.3递归与非递归的区别

你可能会疑惑：“为什么递归版本的归并排序，好像没有这么多复杂的边界判断？

答案的核心的是：递归（自顶向下）拥有 “自动适应” 的灵活性，而非递归（自底向上）则带有 “按规则执行” 的僵硬性—— 两者的核心逻辑差异，直接导致了边界处理的复杂度不同。

3.3.1递归：顺势而为，自然适配

核心思路：不预设任何拆分规则，只遵循 “把当前数组切两半” 的核心逻辑，直到子数组长度为 1（不可再拆）。

关键特点：自动停止，无需刻意判断边界



递归的拆分完全依赖 “当前区间的实际长度”：

        比如数组长度 N=6，会先切成 [0,2] 和 [3,5]（各 3 个元素）；左区间 [0,2] 再切成 [0,0] 和 [1,2]（1 个 + 2 个元素）；右区间 [3,5] 同理切成 [3,4] 和 [5,5]；直到子数组长度为 1（如 [0,0]），递归自然终止（因为 left >= right，不再继续拆分）。



它不关心 “整体数组长度是多少”，只聚焦 “当前手里的区间有几个元素”，拆分过程顺势而为，边界会自然收敛，无需额外处理 “框选超出范围” 的问题。

3.3.2非递归：刻舟求剑，需手动补漏

核心思路：不进行 “拆分”，而是从最小步长（长度 1）开始，按固定规则 “合并”，严格遵循 1→2→4→8→… 的翻倍逻辑，用固定尺寸的 “框” 去框选相邻子数组进行合并。

关键特点：规则固定，必须处理边界溢出



非递归的合并规则是 “僵硬” 的，固定尺寸的 “框”（gap）不会因数组长度调整：

        比如数组长度 N=6，当 gap=4 时，按规则会尝试框选 [0,3] 和 [4,7] 两个区间合并；但数组实际长度只有 6，[4,7] 会超出数组边界（最大索引为 5），此时必须手动判断并修正右边界（比如将 end2 设为 N-1=5）。



这种 “按固定规则框选” 的逻辑，就像 “刻舟求剑”—— 不管数组实际长度是否匹配，先按规则执行，再处理因 “框太大” 导致的边界溢出问题，这也是非递归版本需要额外边界判断的核心原因。

四、代码实现

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; printf("\n"); } free(tmp); }

既然看到这里了，不妨关注+点赞+收藏，感谢大家，若有问题请指正。