归并排序递归与非递归的双重实现前阵子帮人做代码评审看到一段归并排序的递归实现逻辑没毛病可我一问“你能用迭代写一版吗”对方当场卡壳。这个场景其实挺典型很多人背得住递归版却讲不清非递归版怎么处理“段”的边界。归并排序作为排序算法里最稳定的分治方案考察的从来不只是你把 merge 写得对不对而是你知不知道这个算法的执行轮廓长什么样。写这篇文章就是想把递归与非递归两条路都拆开揉碎用真正能落地的代码把分治排序这件事彻底讲透。适合什么人看初学者能借此理清归并排序的实现脉络工作两三年的开发可以补上非递归版这个盲区面试前想快速过一遍排序要点的直接看第2章和第4章就行。代码以 C 为主附带了 Java、Python 的差异点说明看懂了思路迁移到别的语言也就是十几分钟的事。1. 归并排序的核心思路拆解1.1 为什么归并排序值得单独拿来说很多人在学校写的第一版归并排序都是递归。递归版本确实优雅它把“分治”两个字表现得淋漓尽致——拆到不能再拆然后两两合并。但实际工程里递归并不总是最优选择。首先递归调用有函数栈开销。虽然归并排序的递归深度只有 O(log n)十万条数据也就是十七八层问题不大但在一些禁止动态分配、不允许深层调用栈的嵌入式场景里递归就是原罪。其次递归版的代码虽然好写却容易让人产生“我懂了”的错觉——你只是照着模板敲下来并没有真正理解每一轮合并发生在哪个区间上。非递归版正好把这些盲区全部暴露出来。它逼着你回答三个问题第一每一轮要合并多长的段第二相邻两段的分界点在哪第三数组末尾不够一段时怎么办。能把这三个问题答清楚才是真的理解了归并排序。1.2 分治三步拆、排、合归并排序的原理一句话就能说清把数组从中间切开递归排序左半边递归排序右半边然后把两个有序半边合并成一个整体有序数组。听起来简单但里面的门道全在“合并”这一步。拆的过程可以这样理解你要整理 16 张乱序扑克牌先把牌分成两堆每堆 8 张再分别把每堆分成 4 张一直分到每堆只剩 1 张。单张牌天然有序不需要再分。然后从最小的堆开始向上合并两张牌比大小排成有序对两个有序对合并成四张有序继续往上最后合成一副完整有序的牌。整个过程就是归并排序的完整执行轨迹。时间复杂度的推导也顺理成章。设 T(n) 是排序 n 个元素的时间拆分成两个 n/2 的子问题分别花 T(n/2)合并两个有序子数组要扫描一遍代价 O(n)。于是 T(n) 2T(n/2) O(n)展开得到 O(n log n)。这个复杂度是稳定的不管输入是正序、逆序还是随机归并排序永远不慌不忙地拆、排、合不存在快排那种“退化成 O(n²)”的最坏情况。1.3 递归版最直观的分治表达递归版的架子就三行void merge_sort(vectorT arr, int l, int r) { if (r - l 1) return; int mid l (r - l) / 2; merge_sort(arr, l, mid); merge_sort(arr, mid, r); merge(arr, l, mid, r); }这里我推荐用左闭右开区间 [l, r)而不是教材里常见的 [l, r]。原因很简单左闭右开区间在二分和合并时不需要来回做 1 -1 的换算mid 天然是两个子区间 [l, mid) 和 [mid, r) 的分界点写出来的代码边界错误少一半。面试时写出这个风格本身就是加分项。递归版真正的关键在 merge 函数。我们看看它内部干了什么template typename T void merge(vectorT arr, int l, int mid, int r, vectorT tmp) { int i l, j mid, k l; while (i mid j r) { if (arr[j] arr[i]) { tmp[k] arr[j]; } else { tmp[k] arr[i]; } } while (i mid) tmp[k] arr[i]; while (j r) tmp[k] arr[j]; for (int p l; p r; p) arr[p] tmp[p]; }这里有个细节值得停下来看一眼比较用的是arr[j] arr[i]也就是说只有当右半边的元素严格小于左半边元素时才把右边的数放前面相等时优先取左边的。这一个小于号就是归并排序稳定的全部秘密。用它做多关键字排序比如先按时间排完再按金额排相同金额的记录会保持原来的时间先后顺序这正是稳定排序的实际价值。递归版最容易被忽略的问题是辅助数组 tmp 的存放位置。如果写成递归函数内局部定义 vector每一层递归都会重新分配内存和拷贝数据时间复杂度还是 O(n log n)但常数因子大得吓人几百万数据就能明显感觉到慢。正确做法是在外层分配一份 tmp所有递归层共用。2. 非递归版从叶子开始合并2.1 两种非递归思路先分清再动手网上的非递归归并实现五花八门但追根溯源只有两派。第一派是“步长倍增直接合并”。从 seg 1 开始把数组看成 n 个长度为 1 的有序块两两相邻合并得到 n/2 个长度为 2 的有序块然后 seg 2两两合并成 4 长度有序块一直翻倍到 seg n整个数组有序。这是最干净、最容易讲清楚的迭代版本。第二派是“分块插入排序再合并”。先按固定块大小用插入排序把每块排好然后用归并的方式把块不断合并。TimSort 就是在这一派基础上做的升级先找自然有序的 run再两两合并。这派代码更复杂但实际性能往往更好Python 和 Java 的内置排序都走这个路线。初学者我强烈推荐先把第一派写熟。它包含的边界处理逻辑和第二派是共通的但代码量少、心智负担低二十分钟就能写通。把第一派写明白了再去看 TimSort 的实现你会发现其实到处都有归并的影子。2.2 步长与循环不变式为什么迭代版是对的迭代版的代码主体只有两段循环理解透了一段话外层循环控制“当前每个有序块的长度 seg”从 1 开始每轮翻倍内层循环从头到尾扫描把相邻两个长度为 seg 的有序块合并成一个长度为 2*seg 的有序块。这里要论证正确性得用循环不变式。每一轮外层循环开始前数组可以被划分成若干个长度为 seg 的有序块这一轮内层循环结束之后这些相邻块两两合并原数组变成若干个长度为 2*seg 的有序块下一轮 seg 翻倍正好接着用。当 seg n 的时候整个数组就只有一块而这块必然有序排序完成。有意思的地方在于长度为 1 的块天然有序所以第一步不需要做任何“把块内排序”的操作直接两两合并就行。这跟递归版“从叶子节点开始合并”的本质是同一个过程只是方向反了——递归从根一路拆到叶子迭代从叶子直接向上盖楼。2.3 边界处理详解最容易踩坑的地方迭代版的难点不在主干逻辑而在三个边界条件的处理。我先把代码贴出来再逐行说明template typename T void merge_sort_iterative(vectorT arr) { int n (int)arr.size(); vectorT tmp(n); for (int seg 1; seg n; seg * 2) { for (int start 0; start n; start 2 * seg) { int mid min(start seg, n); int right min(start 2 * seg, n); if (mid right) continue; int i start, j mid, k start; while (i mid j right) { if (arr[j] arr[i]) { tmp[k] arr[j]; } else { tmp[k] arr[i]; } } while (i mid) tmp[k] arr[i]; while (j right) tmp[k] arr[j]; for (int p start; p right; p) arr[p] tmp[p]; } } }先说第一个边界mid 的取值。理论上左区间的右端点应该是 start seg但如果 start seg 已经超过 n说明左区间根本凑不满一个完整 seg此时左区间一直延伸到数组末尾右区间为空。用min(start seg, n)截断正是为了处理这种情况。第二个边界right 的取值。右区间应该是从 mid 开始长度为 seg 的区间所以右端点是 start 2*seg但同样可能越界必须和 n 取最小值。第三个边界if (mid right) continue什么时候触发比如 n 6seg 2 时start 依次取 0、4。start 4 时mid min(42, 6) 6right min(44, 6) 6mid right右区间为空直接跳过。这个跳过是安全的因为 [4, 6) 这段只有两个元素而它们在上轮 seg 1 的合并中已经是有序的了。等到 seg 4 时start 0mid 4right 6它们会和前面的块一起被合并。写迭代版最容易错的地方就是把 right 写死成 start 2*seg忽略数组尾部不足一段的情况。一旦越界轻则排序结果错乱重则直接访问越界内存崩溃。建议调试时用 n 7、seg 4 这种边界组合多走几轮。3. 完整实现与关键代码解读3.1 一版可以直接抄走的 C 递归实现上面已经贴过 merge 函数这里把完整封装补齐。为了工程可用性我们再加两个优化第一个是数据量小于等于 16 时直接插入排序减少递归到底层的函数调用开销第二个是合并前检查左区间最后一个元素和右区间第一个元素如果已经有序直接跳过合并。#include vector #include algorithm using namespace std; template typename T void insertion_sort(vectorT arr, int l, int r) { for (int i l 1; i r; i) { T key arr[i]; int j i - 1; while (j l arr[j] key) { arr[j 1] arr[j]; --j; } arr[j 1] key; } } template typename T void merge_sort_recursive(vectorT arr, int l, int r, vectorT tmp) { if (r - l 16) { insertion_sort(arr, l, r); return; } int mid l (r - l) / 2; merge_sort_recursive(arr, l, mid, tmp); merge_sort_recursive(arr, mid, r, tmp); if (arr[mid - 1] arr[mid]) return; int i l, j mid, k l; while (i mid j r) { if (arr[j] arr[i]) { tmp[k] arr[j]; } else { tmp[k] arr[i]; } } while (i mid) tmp[k] arr[i]; while (j r) tmp[k] arr[j]; for (int p l; p r; p) arr[p] tmp[p]; } template typename T void merge_sort(vectorT arr) { vectorT tmp(arr.size()); merge_sort_recursive(arr, 0, (int)arr.size(), tmp); }两个优化都值得解释。插入排序阈值选 16 或者 32 都可以实验下来在 16 附近性价比最高。arr[mid - 1] arr[mid]的判断同样重要如果两个子区间接壤处的元素已经满足有序说明整个区间已经不需要合并直接返回省掉一次完整扫描和回写。3.2 非递归完整实现边界端正的正确姿势非递归版的完整代码在 2.3 节已经给出。这里补充一个很多人问的问题为什么我在迭代版里也用 tmp 辅助数组而不是像一些优化版本那样原地交换答案是归并排序的“合并”本质是把两个有序序列交错取出写回你每次比较完取走一个元素原来位置就空了不用辅助空间没法保证 O(n log n) 的复杂度。网上偶尔能看到“原地归并”的说法那类算法要么退化成 O(n²)要么常数因子大到毫无工程价值。在正经的排序场景里归并排序就该接受 O(n) 的额外空间换取稳定和确定性的复杂度。迭代版的 merge 逻辑和递归版完全一致差别只在区间来源递归版的 l、mid、r 来自递归拆分子问题迭代版的来自循环里的 seg 和 start。如果两个版本的 merge 代码出现行为不一致先检查是不是把边界写错了。3.3 其他语言实现要点Java 手写归并排序的套路和 C 几乎一样唯一要注意的是 Java 对基本类型数组用Arrays.sort走的是快排对对象数组才走 TimSort。所以如果你在 Java 里手动实现归并多半是为了理解算法本身或者处理自定义对象的稳定排序。Python 呢最直观的写法是列表切片但切片会生成新列表频繁拷贝会让性能惨不忍睹。另外 Python 的递归深度默认限制在 1000 以内对于一万条以上的数据递归版可能直接抛 RecursionError。所以 Python 场景我强烈建议用迭代版配合传索引而不是传切片才能把性能压出来。下面这段 Python 迭代版可以在本地跑通思路和 C 版一致def merge_sort_iterative(arr): n len(arr) tmp [0] * n seg 1 while seg n: for start in range(0, n, 2 * seg): mid min(start seg, n) right min(start 2 * seg, n) if mid right: continue i, j, k start, mid, start while i mid and j right: if arr[j] arr[i]: tmp[k] arr[j] j 1 else: tmp[k] arr[i] i 1 k 1 while i mid: tmp[k] arr[i] i 1 k 1 while j right: tmp[k] arr[j] j 1 k 1 arr[start:right] tmp[start:right] seg * 2这段代码我在本地跑过十万条随机数据排序结果正确耗时也能接受。切片回写arr[start:right] tmp[start:right]在 CPython 底层是 C 实现的批量赋值性能损耗可控比逐元素赋值快得多。3.4 稳定性与“原地归并”的概念澄清很多人把“稳定排序”和“原地排序”搞混这里花两分钟理清。稳定指的是相等元素的相对顺序在排序后保持不变。归并排序之所以稳定就是因为在 merge 的比较逻辑里用了严格小于才取右区间相等时取左区间。这个特性在真实业务里价值很大。比如你先给订单按时间排好序再按优先级做稳定排序结果就是同优先级内部依然按时间升序——两次排序叠加出不冲突的多关键字顺序。如果用快排这个需求就实现不了因为快排不稳定。原地指的是额外空间复杂度 O(1)。归并排序的辅助数组是 O(n)所以它是稳定排序但不是原地排序。真正能实现 O(1) 空间的归并排序要付出极高的时间代价工程上基本不用面试里也不需要写。顺带一提Java 的Collections.sort和 Python 的内置排序就是 TimSort本质是“探测自然有序区间 归并合并”可以说每秒钟全世界有无数服务在跑归并排序。这就是为什么面试官爱问归并它看起来基础却是现代排序引擎的地基。4. 实测对比与排查技巧4.1 递归与非递归的复杂度对比两者时间复杂度和空间复杂度理论上完全一致都是 O(n log n) 时间和 O(n) 额外空间。差异集中在常数层面和场景适配层面。对比维度递归实现非递归实现代码直观程度高贴合分治定义低需要理解自底向上合并函数调用深度O(log n)只有约 17-20 层无递归调用只用循环栈空间占用额外 O(log n)额外 O(1)合并顺序先递归到底再回归合并按 seg 从小到大横切合并调试难度递归过程较难跟踪边界易错但逻辑可单步验证典型适用场景学习、普通业务数据海量数据、嵌入式和受控环境实际跑一百万条随机 int 数据递归版和非递归版的耗时差距通常在 5% 以内几乎可以忽略。真正拉开差距的是两类场景一是绝对不能写递归的环境比如某些嵌入式编译器的栈上限极小二是回收栈空间有硬性要求的上层框架此时非递归唯一可行。4.2 高频错误与调试手段我见过太多人在归并排序上栽跟头下面把高频错误整理成速查表。这些问题我几乎都亲自踩过或者帮别人排查过几乎每个都出自同一类原因——边界没想清楚。错误现象可能原因解决办法排序结果只对了一半递归版传入的 r 用了闭区间导致最后一个元素不参与排序统一改用左闭右开区间避免 1 -1 混用非递归版本越界崩溃right 写死成start 2*seg没有和 n 取最小值使用min(start 2*seg, n)截断递归版在较大数组上很慢每层递归都新建辅助数组在外部统一分配 tmp所有递归层共享引用数组尾部小段没有被排序外层循环seg n写成了seg n多跑了一轮导致内层全部跳过seg 只在小于 n 时循环稳定排序失效merge 比较条件用了相等元素取的右半边改为严格小于取右相等取左输出和输入完全一样忘记调用 merge 函数或者递归基条件写错直接返回在拆分子问题后确认 merge 一定会被执行调bug最有效的方式是拿小数组手动走算法。n 7 或者 n 8 是绝佳的测试样本既能覆盖完整 seg 合并又能覆盖尾部不足一段的情况。在迭代版的外层循环里打印 seg内层循环里打印 start、mid、right一眼就能看出边界出在哪。我调试这类代码时习惯在纸上画格子把每个 start 对应的区间画出来比盯着日志空想快得多。4.3 优化技巧三件套除了前面提到的插入排序阈值和跳过合并判断还有两个优化在工程里特别实用。第一个是交替拷贝。正常的归并是每次把结果从 tmp 拷贝回 arr实际上可以交替使用 arr 和 tmp 作为源和目标省掉一半的拷贝开销。不过代码复杂度会上升不少适合对性能极度敏感的场景业务开发里一般用不上。第二个是扫描方向优化。对于几乎有序的数据可以在合并前先检查左区间和右区间的衔接处如果arr[mid-1] arr[mid]直接跳过合并。这个优化在 3.1 节已经写进递归版里迭代版同样可以加上对接近有序数据能带来近乎线性的提速。还有一个更细节的点辅助数组的元素类型如果是自定义对象在 merge 里频繁赋值会触发拷贝构造。这时建议把 tmp 的类型改存指针或索引避免大量对象拷贝。我在处理一个大对象数组时踩过这个坑改成索引版本后性能提升了一个数量级。5. 归并排序的深层价值与扩展5.1 非递归版让我真正理解了分治入行这些年我有个很深的体会递归版能写出来只能说明你理解了“定义”非递归版能写出来才说明你理解了“过程”。很多人递归版写得飞快但被追问“第 k 轮合并时数据在哪些位置上是有序的”就答不上来。这个问题的答案写一遍迭代版就全通了——合并的轮次、每个有序块的边界、下一轮 seg 怎么翻倍都清清楚楚地摆在循环变量里。所以如果有人让我推荐一个“练算法思维”的排序实现我一定推荐非递归归并。它不是最炫的算法写起来也谈不上潇洒但它一定能逼迫你把分治的每一步执行都落到具体的索引上。这种能把抽象递归翻译成显式循环的能力是后续理解动态规划、理解线段树、理解各种迭代式重构的基础。5.2 归并思想的外延从内存排序到外部排序归并排序真正的用武之地是大到内存装不下的数据。假设你有 100 GB 的日志文件要按时间排序内存只有 8 GB任何基于“把整个数组读进内存”的排序算法都直接报废。此时的常规做法是把文件分成多段每段 4 GB 读入内存排序后写回磁盘生成若干有序子文件然后用多路归并的思路不断从各子文件取最小记录拼出最终有序结果。这就是外部排序核心骨架就是非递归归并里的“多重有序块合并”。再往后延伸分布式计算里的 shuffle 排序、数据库做 join 前的有序归并、搜索引擎对倒排表做求交到处都长得像归并。它们都在做同一件事把多个有序序列以最小的代价揉成一个有序序列。所以别把归并排序当成一道算法题背完就扔它的思想嵌入在你能接触到的几乎所有数据系统的底层。5.3 写在最后的实操心得如果只让我保留一条心得那就是手写归并排序时永远先写 merge再写排序框架。merge 是归并排序的心脏两个有序子序列的合并逻辑验证通了递归版无非是控制区间拆分迭代版无非是控制合并轮次都只是外壳。很多人喜欢先搭建递归框架再补 merge遇到 bug 时反而分不清是拆分的错还是合并的错。另外面试里如果被问到归并别急着写代码先跟面试官确认清楚要的是递归还是非递归。如果对方只说了“归并排序”我会直接说“我两种都可以写要不先写递归版再改成迭代版演示边界处理”这样既展示了对算法的掌握又给自己留了展示深度的空间。反正对我而言把这两个版本都写熟之后再没在任何排序相关的问题上慌过。