归并排序递归与非递归实现：从分治原理到工程化优化-北京尧图网络

搞过一次大数据量排序之后我才真正意识到递归版归并排序在教学上和工程上完全是两码事。理论课上讲归并排序教科书永远是递归写法简洁漂亮但真到了处理大批量数据的时候频繁的临时数组分配和函数调用开销会让人想把代码整个推翻。后来我把递归版改成非递归版整个排序过程的内存分配降到一次逻辑也变得更可控这才算把“归并排序——递归与非递归的双重实现”这块骨头啃透了。这篇文章我会把两种实现从核心原理到完整代码、再到边界推导全部拆开讲最后补上工程中的优化经验和选型建议。无论你是刚学数据结构、正在准备面试还是需要在项目里自研一个排序组件都应该能从里面找到直接能抄走的东西。1. 归并排序到底在归并什么有序区间合并这件事归并排序的英文名是 Merge Sort它的要害就在 Merge 这个词上。和快速排序那种“边划分边排序”的思路不一样归并排序先把数组切碎再靠一次次有序合并把整个数组拼回有序。理解了这个操作后面递归和非递归两种写法都只是“怎么安排合并次序”的问题。1.1 两路归并把两个有序序列合成一个有序序列假设我有两个已经排好序的数组左边是 [1, 3, 5]右边是 [2, 4, 6]要把它们合并成一个大的有序数组。做法很直观同时看两边的头部元素谁小就先取谁。第一次比 1 和 2取 1第二次比 3 和 2取 2第三次比 3 和 4取 3以此类推最后剩下的 6 直接收尾。合并结果是 [1, 2, 3, 4, 5, 6]。这个过程的时间复杂度是线性的 O(n)因为每个元素最多被比较和搬运一次。你可以把它想象成两堆已经按大小叠好的扑克牌每次只看两堆最上面那一张抽出更小的一张放到结果堆。整个过程只需要反复“看牌堆顶、抽牌”不需要跳来跳去。归并排序的整体策略也就清楚了一个无序数组先切成两半把左半边排好再把右半边排好最后用这个合并操作把两个有序半边拼起来。切到什么时候为止切到子数组只剩一个元素的时候单个元素天然有序直接返回。这就是所谓的分治思想——把大问题拆成两个结构相同的小问题小问题解决后再把答案合起来。1.2 merge 函数的实现细节merge 就是把上面这套“两路归并”落成代码。给定一个数组 arr、左边界 left、中间位置 mid、右边界 right并且保证 arr[left..mid] 和 arr[mid1..right] 都已经升序merge 负责把整个区间变成升序。基础版本如下private static void merge(int[] arr, int left, int mid, int right) { int[] temp new int[right - left 1]; int i left, j mid 1, k 0; while (i mid j right) { if (arr[i] arr[j]) { temp[k] arr[i]; } else { temp[k] arr[j]; } } while (i mid) { temp[k] arr[i]; } while (j right) { temp[k] arr[j]; } for (int p 0; p temp.length; p) { arr[left p] temp[p]; } }我见过不少初学者在这里写arr[i] arr[j]少了一个等号这是会破坏稳定性的。归并排序是稳定排序所谓稳定是指如果两个元素相等它们排序后的相对位置和排序前保持一致。所以遇到相等元素时必须先取左半部分那个也就是要写成而不是。temp 数组是每次 merge 临时开辟的这一步后面要重点优化。最后那个循环负责把临时数组里的数据写回 arr 的对应区间如果漏掉它合并结果只会留在 temp 里下一轮排序根本用不上。1.3 稳定性的来源和意义像快速排序、堆排序这类算法遇到相等元素时顺序可能被打乱叫不稳定排序。归并排序天然稳定靠的就是上面那句。稳定到底有什么用举一个最简单的例子一批订单先按时间排序然后希望按用户 ID 分组同时要求同一个用户下的订单仍然保持时间顺序。如果你用不稳定的快排按用户 ID 排时间顺序会被打乱用稳定排序按用户 ID 排相同用户 ID 的记录会保持原来的时间顺序。很多多字段排序场景都有这个需求后面第 6 节还会展开讲。2. 递归实现自上而下的分治代码最直观递归版归并排序是数据结构教材里的常客因为它把分治思想表达得最直接。先把大数组切成两半排序再合并代码结构几乎就是把思路翻译了一遍。2.1 递归的三个基本要素写任何递归都要先回答三个问题终止条件是什么子问题怎么划分子问题的结果怎么合并归并排序的答案是终止条件left right区间为空或只有一个元素天然有序直接返回。子问题划分取中点 mid排序左半区间[left, mid]再排序右半区间[mid1, right]。结果合并调用 merge把两个有序子区间合并成一个。代码很短public static void mergeSortRecursive(int[] arr, int left, int right) { if (left right) { return; } int mid left ((right - left) 1); mergeSortRecursive(arr, left, mid); mergeSortRecursive(arr, mid 1, right); merge(arr, left, mid, right); }注意 mid 的写法。很多同学习惯直接写(left right) / 2这在 left 和 right 都是接近上限的整数时left right可能溢出变成负数索引程序直接崩。用left ((right - left) 1)或者left (right - left) / 2都能避开这个问题。工程代码里养成这个习惯不亏。2.2 递归调用过程怎么展开用数组[38, 27, 43, 3, 9, 82, 10]举例。初始 left0, right6, mid3。程序会先递归排序左半边[0..3]这个过程又拆成[0..1]和[2..3]。[0..1]再拆成[0]和[1]两个单元素区间直接返回然后合并出[27, 38]。[2..3]类似合并出[3, 43]。再合并[0..3]得到[3, 27, 38, 43]。右边[4..6]也这样处理最后把两个大有序区间合并整个数组有序。从调用轨迹看递归版是深度优先的。它会先把左半边彻底排好再去碰右半边。每次 merge 发生时参与合并的两个子区间都已经全局有序所以 merge 里只需要线性比较就好。2.3 递归版真正让人不舒服的地方递归版逻辑清楚但工程上不是没有代价。第一每次递归调用都有栈帧压栈、弹栈以 100 万元素为例mergeSort 函数大概会被调用 200 万次。第二如果直接用最基础版的 merge每个 merge 都会 new 一个临时数组小数组反复分配大数组一次分配大块内存GC 压力非常明显。我前面提到那个数据处理任务跑完一次排序内存曲线像锯齿一样就是这里造成的。当然递归深度本身只有 O(log n)以 10 亿数据量来算也就 30 层左右所以“递归导致栈溢出”在归并排序里通常是伪命题。真正需要关注的是函数调用开销和临时数组分配这一点决定了后面非递归版本值得认真学习。3. 非递归实现自底向上的宽度翻倍边界是重头戏非递归版归并排序也叫自底向上归并。它不递归切分而是直接把每个元素看成有序区间然后从长度为 1 的区间开始相邻两个区间一轮一轮地合并区间宽度每次翻倍。3.1 从“切分”改成“拼接”递归版是先决定一个大区间然后一层层往下切非递归版反过来先处理最小区间再逐步扩大合并粒度。外层循环一个变量 width表示当前这轮合并时每个有序区间的基础长度。第一轮 width 1相邻的两个单元素合并成有序对第二轮 width 2相邻的两个有序对合并成 4 个元素的有序块第三轮 width 4以此类推。当 width 超过数组长度 n 时整个数组已经在一个大有序区间里排序完成。3.2 迭代版核心代码public static void mergeSortIterative(int[] arr) { int n arr.length; for (int width 1; width n; width 1) { for (int start 0; start n - width; start width 1) { int mid start width - 1; int end Math.min(start (width 1) - 1, n - 1); merge(arr, start, mid, end); } } }这段代码不长但内层循环的三个边界表达式第一次接触的人几乎都会写错。我建议你不要直接背而是推一遍。3.3 边界条件推演为什么是 n - width先说start n - width。start 是左半区间的起点这个条件保证左半区间存在并且右边至少还有一个元素可以跟它合并。如果 start 已经大于等于n - width说明剩下的元素不足一个 width根本不存在右半区间强行合并就会越界。再看mid start width - 1。这是左半区间的末尾。因为 start 最大是n - width - 1所以 mid 最大是n - 2不会越界右边至少还有一个元素 index n - 1。最后看end Math.min(start 2 * width - 1, n - 1)。右半区间的理论末尾是start 2 * width - 1但数组长度不一定是 2 的幂末尾可能不够宽所以必须用 min 截断到 n - 1。这样最后一次合并就可以处理“左侧完整、右侧残缺”的情况。拿 n 5 的数组[a, b, c, d, e]走一遍width1合并[0..1]a、b合并[2..3]c、de 落单不处理。start0 时 mid0, end1start2 时 mid2, end3start4 不满足 start 4循环结束。width2start0 时 mid1, end3合并[0..3]即有序的[a,b]和有序的[c,d]合并e 落单。width4start0 时 mid3, end4合并[0..3]和[4]把 e 也拼进来完成后整个数组有序。注意一个细节非递归版处理“长度不是 2 的幂”时靠的是 end 截断而不是往数组后面补哨兵。有些写法喜欢补一个无穷大把长度凑成 2 的幂这在业务数据不可控时很容易出问题后面讲哨兵坑的时候会细说。非递归版的中间状态也很有意思每一轮结束后数组里所有宽度相同的区间各自有序但块与块之间未必有序。这和递归版那种“左半边先完全有序”的中间态完全不同。对于最终排序结果没有影响但在某些增量排序场景下这种规整的中间状态更好描述、更好恢复。4. 递归与迭代的全面对比复杂度、顺序与调用开销两种实现底层共享同一个 merge稳定性完全一致差别主要集中在调用方向、辅助空间和中间状态上。4.1 复杂度时间都是 O(n log n)空间差在递归栈时间复杂度上两者都是 O(n log n)。每一轮合并的总规模是 n区间宽度每轮翻倍轮数是 log n所以总工作量是 O(n log n)。最关键的是归并排序的最好、最坏、平均时间复杂度都是 O(n log n)这一点比快速排序稳定得多——快排最坏会退化到 O(n²)归并不会。空间复杂度略有差别。递归版如果每次都 new 临时数组空间峰值是 O(n)但递归栈额外占 O(log n)。非递归版没有递归栈临时数组 O(n)合起来仍然是 O(n)。真正影响体验的不是栈深而是临时数组的分配次数。基础版 merge 每次调用都 new 一次百万数据量的递归版会分配超过一百万个临时数组尽管大多数很小但 GC 压力实实在在。对比项递归版非递归版划分方向自顶向下先拆分后合并自底向上直接合并递归栈占用O(log n)无调用顺序深度优先先排整个左半边每轮从左到右等宽区间各自有序边界处理难度低高容易漏边界代码可读性高中稳定性稳定稳定内存分配次数取决于 merge 实现取决于 merge 实现4.2 合并顺序差异带来什么递归版是深度优先从根节点出发一路递归到最左边的单元素然后一层层合并把整个左半边排好才转向右半边。如果你在排序过程中打印数组会看到左边逐渐有序右边还保持原样。非递归版是“分层推进”第一轮结束所有相邻元素组成有序对第二轮结束所有长度为 4 的块有序第三轮结束所有长度为 8 的块有序。这种访问模式对 CPU 缓存很友好因为每一轮都是从头到尾线性扫描数组几乎没有随机跳跃。递归版的访问是跳跃式的虽然局部性也不算差但层级切换更多。实测大数组上非递归版通常会快一点点但差距一般不大并不是换一个版本就天翻地覆。另外一个容易被忽略的差异是“可中断性”。如果排序允许被打断比如排序超过时间预算就先保存中间状态非递归版每轮结束后的状态是一个清晰可描述的稳定态恢复起来很容易递归版的中间态则是一棵没走完的递归树。虽然实际排序很少这么干但理解这点对设计增量排序有启发。4.3 选型建议教学、面试、写算法题用递归版就好思路清晰不容易错。自研排序工具、嵌入式环境、数据量大且对调用开销敏感优先上非递归版。如果再叠加下一节说的临时数组复用非递归版在工程上的优势会更明显。5. 实战优化临时数组、哨兵与小区间切换到这里两种写法都会了但直接拿去生产环境还不够。下面这几个优化点是我实际排序时踩过的坑或者切实收益最大的改法。5.1 一次分配临时数组复用到最后这是归并排序最重要的工程优化。基础版 merge 每次都 new 一个数组改成在排序入口只分配一次长度为 n 的 temp所有 merge 共用private static void mergeWithTemp(int[] arr, int[] temp, int left, int mid, int right) { int i left, j mid 1, k left; while (i mid j right) { if (arr[i] arr[j]) { temp[k] arr[i]; } else { temp[k] arr[j]; } } while (i mid) { temp[k] arr[i]; } while (j right) { temp[k] arr[j]; } for (int p left; p right; p) { arr[p] temp[p]; } }入口处只分配一次public static void mergeSort(int[] arr) { int[] temp new int[arr.length]; mergeSortRecursive(arr, temp, 0, arr.length - 1); }这个 merge 版本和基础版思路一致只是把临时数组从“每次新开”变成“全程复用”。它直接读取 arr 上两个有序子区间写入 temp最后整体回写 arr。有人担心合并过程中 temp 的数据会不会覆盖 arr 还没读到的元素——不会因为 temp 是独立数组读写互不干扰读区永远是 arr 上两个不相交的有序段写区永远是 temp。最后回写时arr 对应区间被整体更新成有序版本后续合并继续读它逻辑闭环。还有一种常见写法先把arr[left..right]整体拷到 temp再从 temp 里取两段比较写回 arr。两种都对性能差距很小。我这里选的版本少了一次批量拷贝但可读性略低看个人喜好。5.2 哨兵值的坑不少教材为了简化 merge 里的 while 判断会在左右两个子数组末尾放一个“无穷大哨兵”这样不需要判断指针是否越界比较到哨兵自然收尾。思路巧妙但工程里我不推荐原因有三。第一数据里如果本身就有Integer.MAX_VALUE哨兵就失效了合并逻辑可能在相等值上出错。第二排序对象数组时哨兵不好定义用 null 做哨兵又容易在比较时触发空指针。第三哨兵只是省掉几次越界判断收益很小却给排序组件引入了“数据范围必须小于哨兵”的隐含约束。我的习惯是基础组件排序正确性优先于微优化条件判断写全不用哨兵。真要追求那点常数先把临时数组复用和小区间插入排序做了收益大得多。5.3 小区间切换插入排序归并在递归到很小区间时比如元素个数少于 16继续递归调用和分配临时数组的开销反而比简单排序高。插入排序在小区间上常数极小没有递归调用代码也简单。工程实现里会在递归版里加一个阈值private static final int THRESHOLD 16; public static void mergeSortRecursive(int[] arr, int[] temp, int left, int right) { if (right - left THRESHOLD) { insertionSort(arr, left, right); return; } int mid left ((right - left) 1); mergeSortRecursive(arr, temp, left, mid); mergeSortRecursive(arr, temp, mid 1, right); mergeWithTemp(arr, temp, left, mid, right); }插入排序代码private static void insertionSort(int[] arr, int left, int right) { for (int i left 1; i right; i) { int key arr[i]; int j i - 1; while (j left arr[j] key) { arr[j 1] arr[j]; j--; } arr[j 1] key; } }阈值选在 8 到 32 之间都是常见做法。别小看这一步它能省掉大量最底层的递归调用实测对中等规模乱序数组有明显提升。5.4 自然归并利用原本就有的有序片段非递归版默认从 width 1 开始等于把每个单元素都当成一个有序段。但如果输入数据里本来就有一段段升序子序列从 1 开始就浪费了更早的信息。自然的做法是先扫描一遍数组把连续升序片段识别成初始有序段。比如[1, 3, 5, 2, 4, 8, 0]扫描完得到初始段[1,3,5]、[2,4,8]、[0]三段合并时从这三段开始而不是从 8 个单元素开始。数据越接近有序收益越大。像 Java 和 Python 标准库底层用的 TimSort核心思想就是自然归并加二分插入排序能让接近有序的输入跑到接近 O(n) 的时间。想深入了解归并优化的同学研究 TimSort 是很值得的下一步。6. 工程选型稳定排序、语言标准库与外部排序归并排序在算法书里看起来是个“基础排序”但真正到了工程里它的地位远比想象中高。6.1 标准库里的归并排序很多语言的排序接口都内置了归并思想。Java 里排序对象数组用的Arrays.sort(Object[])是稳定的 TimSort 变种Collections.sort()同理排序基本类型数组的Arrays.sort(int[])用的却是双轴快排因为基本类型的相等没有“相对顺序”概念不需要稳定。C 的std::stable_sort是稳定排序通常由归并实现std::sort是不稳定的内省排序。Python 内置的list.sort()和sorted()也是稳定的 TimSort。你可能会疑惑标准库都封装好了为什么还要自己写两个原因一是面试和算法题经常要求手写二是有些场景标准库帮不上忙最典型的就是数据量大到内存装不下必须自己实现外部排序流程。6.2 什么时候必须用稳定排序回到第 1 节那个稳定性问题。多字段排序时稳定排序能给你省很多组合键的麻烦。比如一批记录先按姓名排再按分数排如果分数相同希望保持姓名的原有顺序稳定排序直接两轮搞定第一轮按姓名排第二轮按分数排。不稳定排序就得把姓名和分数包装成组合键才能保证同样的效果。在面向对象语言里对象字段可能很复杂复制组合键有额外开销稳定排序就显得尤为重要。这也是为什么 Java 对对象数组必须用稳定的归并变种而对基本类型数组反而放心用快排。6.3 外部排序内存装不下时归并几乎是唯一选择归并排序还有一项其他比较排序不具备的能力天然适合外部排序。假设内存只有 1GB要排序一个 10GB 的文件可以这样做把文件切成 10 个 1GB 的块逐块读入内存用任意排序算法排好写回磁盘。对磁盘上多个有序块做多路归并同时打开所有块的输入流每个流维护当前头部元素每次取最小的一个写入输出文件再从那块补充下一个元素。全部写完输出文件就是一个有序大文件。快速排序和堆排序做不到这一点因为它们要求数据能够整体随机访问。而多路归并只需要每个块当前头部的几个元素在内存中配合缓冲区就能稳定工作。数据库的排序算子底层干的就是这回事。多路归并还有个进阶话题当路数 K 很大时每次从 K 个头部里选最小值用线性扫描成本高常见优化是维护一个大小为 K 的堆或败者树把单步代价降到 O(log K)。这个东西展开可以单独写一篇这里你只需要记住结论归并排序能撑起从几千到几亿数据的排序场景靠的就是稳定和可外部化这两个特性。我自己动手实现排序的时候有个固定套路面试和快速验证思路用递归版因为不容易写错真正要放进项目里跑的代码用非递归版配一次 temp 复用再根据数据规模决定要不要加小区间插入排序。归并排序最值得记住的从来不是某段具体代码而是“稳定排序”和“外部排序可行”这两个能力它们让这个几十年前的老算法在今天的大数据和数据库场景里依然是核心角色。如果你正准备手写一个排序先想清楚数据能不能全放进内存需不需要保持原有相对顺序这两个问题的答案会直接帮你决定该选归并还是快排。

归并排序递归与非递归实现：从分治原理到工程化优化

相关推荐

函数是Python编程的核心构建块，也是程序设计中实现代码复用、模块化和抽象化的重要手段

切片级漏洞检测：用GNN实现函数内精准漏洞定位

企业虚拟办公AI平台五层架构设计与落地实践

更多资讯

类模板偏特化完全指南：从语法到实战掌握编译期分派

CalculiX ccx-2.11开源CAE求解器编译与接触非线性实战指南

教学锚定的代码聚类：从形态分组到可解释的学情分析

实体验证分层设计：从if-else堆判断到可落地的校验体系

用 WebView2 给传统 Win32/C++ 程序补现代 UI：完整接入路径与踩坑复盘

PyTorch LSTM调制识别实战：RML2016-10a信号分类

今日更新

金融AI落地指南：从调研报告到技术选型与工程实践

大模型上下文成本与注意力优化技术深度解析——为何O(n²)平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测

基于GMM的语音识别系统原理与MATLAB实现详解

本周精选

金融AI落地指南：从调研报告到技术选型与工程实践

大模型上下文成本与注意力优化技术深度解析——为何O(n²)平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测

基于GMM的语音识别系统原理与MATLAB实现详解

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？