提到归并排序很多人的第一反应是教科书里那个时间复杂度稳定在 O(n log n) 的经典算法面试前背一背模板就过去了。但如果只停留在会写递归、会用辅助数组这个层面你大概率没看到它在真实工程里的分量。我最早对归并排序产生这不是书呆子算法的改观是很多年前在服务器上处理一份接近 2GB 的日志文件——内存根本装不下快排全家桶全都没法直接用最后扛住问题的恰恰是归并排序的分治思想。这篇文章我就围绕归并排序从分治原理、合并细节、复杂度推导到外部排序、多路归并这些工程实战场景完整地整理一遍希望能帮你把这道看似基础但实际非常能打的算法彻底吃透。1. 从一张乱牌说起归并排序到底在解决什么问题1.1 排序问题的规模差异比想象中更现实先从一个反直觉的事实讲起。很多人觉得排序嘛Collections.sort 或 Arrays.sort 一调就完事算法区别没那么大。这种观点在几千条数据的时候确实没什么毛病但当你面对的是百万、千万、甚至上亿条记录时O(n²) 和 O(n log n) 之间的差距就不是快一点的事了而是能不能接受的事。举个具体例子。假设我的机器一秒钟能执行一亿次比较操作排序 100 万个元素冒泡排序这种 O(n²) 的算法大约需要 10¹² 次比较也就是一万秒快三个小时。归并排序这种 O(n log n) 的算法大约需要 2000 万次比较0.2 秒。这就是我只讲归并排序、不讲所有排序的原因基数不同的算法决定了你能不能在合理时间内处理大数据。归并排序之所以被广泛应用于数据库、大数据框架、编程语言底层最核心的原因正是它的时间复杂度对输入数据不敏感永远是 O(n log n)不会出现快排那样最坏掉到 O(n²)的灾难。1.2 分治思想把大问题拆成两个已经解决的小问题归并排序最底层的智慧可以用四个字概括分而治之。假设我要给一组长长的数字排序手动做挺烦。但如果我把这组数字切成两半先让左半边有序、右半边有序那我剩下的工作就变成了把两个有序半区合并成一个有序全区。这里有个容易被忽略的关键认知合并两个有序数组比排序一个无序数组容易得多。为什么因为比较完之后不需要像快速排序那样不停交换分区也不需要像插入排序那样反复搬移数据只需要从头到尾扫一遍谁小取谁即可。这个思想递归地应用到左右半边直到子数组只剩一个元素。一个元素天然是有序的不用排序。所以归并排序的递归代码其实只有两个核心动作往下拆回来合并。拆到底就自然有序一路合并回顶部就是最终结果。提示分治思想是归并排序的灵魂学归并排序的时候别一头扎进代码里先想清楚拆分是递归自动完成的合并才是我真正要写的逻辑后面读代码会顺很多。2. 归并排序的命门合并两个有序数组的做法与细节2.1 一个两堆牌的比喻把合并讲明白合并的逻辑我用生活中的场景来演示。假设桌上有两堆扑克牌每堆都已经按照从小到大排好了现在要把它们合成一堆也保持从小到大。做法非常简单同时看两堆牌最上面最小的那一张。比较之后把较小的一张拿走放到新牌堆的最前面。继续比剩下两堆最上面的牌直到某一堆空了。把另一堆剩下的牌直接全部放到新牌堆后面。这就是双指针合并。在代码里那两堆牌就是两个有序子数组指针指向的是当前还没来得及合并的最小元素位置。每次比较两个指针位置的值把小的复制到临时数组然后对应指针往后移一位。为什么最后哪一堆空了就直接倒剩下因为那一堆剩余元素本来就是有序的且它们的值一定比已经合并进去的所有元素都要大。这个思路非常朴素但朴素不代表简单——合并这一步藏了归并排序竞争 O(n log n) 下限的全部秘密。2.2 手写一次 merge 函数这些细节绕不过去下面是一段标准的合并代码我用左闭右开的方式写即合并区间是[left, mid)和[mid, right)private void merge(int[] arr, int left, int mid, int right) { // left 到 mid-1 是左半区mid 到 right-1 是右半区 int[] temp new int[right - left]; int i left; // 左半区指针 int j mid; // 右半区指针 int 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]; } // 把有序的临时数组拷回原数组 System.arraycopy(temp, 0, arr, left, temp.length); }这段代码里有三个点我特意强调第一为什么用而不是这是稳定性的来源。当左右两个元素相等时先取左半区的那么原本在左边的相同元素在合并后仍然在左边数值相同的记录的相对顺序就不会被打乱。这在实际业务里极其重要——比如先按姓名排序再按年龄排序时如果第二趟排序不稳定第一趟按姓名排好的顺序可能就被搅乱了。第二为什么临时数组长度是right - left因为你合并的区间总共就这么多元素开太多纯属浪费。有些教材里图省事在整个递归过程中复用同一个全局临时数组这当然能降低申请内存的开销但理解时先从每次合并一块区间开一块临时数组开始最清晰。第三边界怎么保证不出问题我特别推荐写左闭右开区间[left, right)因为这样两个子区间的边界天然相接左边是[left, mid)右边是[mid, right)mid既是左边的不动点又是右边的起点。很多越界 bug 都出在到底是 mid-1 还是 mid这种边界混乱上左闭右开能直接消灭这类问题。2.3 稳定性到底有什么用一个业务场景就说明白不结合业务的稳定性讲解都是耍流氓。假设我有一份订单数据先按下单时间排了序现在想按金额排序。如果使用的是稳定排序归并排序那金额相同的订单之间的相对顺序仍然是下单时间从早到晚正好符合按金额为主、时间先后为次的需求。如果使用的是不稳定排序金额相同的订单顺序被打乱用户看到的列表会显得很乱后端想再按时间二次排序都救不回来。归并排序在 Java 的对象排序里被大量使用比如Arrays.sort(Object[])底层用的 TimSort 就是归并排序的改良版稳定是最重要的原因之一。除了稳定性归并排序还特别适合链表、外部排序等场景后面我会慢慢展开。3. 递归版归并排序的完整轨迹拆、排、合三步怎么走3.1 一个能直接跑通的递归实现合并函数有了递归骨架就可以搭起来了。还是左闭右开区间public void mergeSort(int[] arr, int left, int right) { // 只剩一个元素或者区间为空天然有序 if (right - left 1) { return; } // 防止 left right 溢出用这个写法 int mid left (right - left) / 2; mergeSort(arr, left, mid); // 递归排序左半 mergeSort(arr, mid, right); // 递归排序右半 // 左右各自有序合并完成整体排序 merge(arr, left, mid, right); }这段代码只要配合上节的merge方法就能直接跑。它暴露了归并排序的全部结构递归拆到不能再拆然后逐层回归——先让左子区间有序再让右子区间有序最后把两个有序区间合并成一个有序区间。mid left (right - left) / 2这个写法值得说道说道。很多人习惯写(left right) / 2但left right在数组非常大的时候可能超过 int 上限导致溢出变成负数然后整个递归全乱套。用left (right - left) / 2可以彻底规避这个问题这也是 LeetCode 等场景里二分查找的标准技巧。3.2 手动模拟一个数组的完整归并过程代码大概率都能看懂但为了确认懂到能复现我用手动模拟的方式走一遍。考虑数组[4, 2, 7, 1, 5, 3]第一层区间[0, 6)mid 3拆成[0, 3)的[4, 2, 7]和[3, 6)的[1, 5, 3]。第二层左边[4, 2, 7]继续拆成[4]和[2, 7][2, 7]再拆成[2]和[7]。这时候到底了[4]有序[2]和[7]各自有序合并[2]和[7]得到[2, 7]再合并[4]和[2, 7]过程是4 和 2 比取 24 和 7 比取 4左半边空了7 补上。得[2, 4, 7]左半区完成排序。右边[1, 5, 3]同理拆成[1]和[5, 3][5, 3]拆成[5]和[3]合并得[3, 5]再和[1]合并得[1, 3, 5]。最后合并两个有序区[2, 4, 7]和[1, 3, 5]2 和 1 比取 12 和 3 比取 24 和 3 比取 34 和 5 比取 47 和 5 比取 5最后 7 补上。最终结果[1, 2, 3, 4, 5, 7]。整个过程中发现了吗所有真正的排序动作都发生在 merge 里递归本身只是在帮你把子问题切到足够小。理解这一点你就理解了归并排序 80% 的精髓。经验如果任何时候怀疑自己的 merge 写得不对就先跑这个 6 元素的小数组手动打印每一层合并后的结果很快就能定位问题。3.3 递归的代价不是所有场景都适合无脑递归递归版本的归并排序虽然清晰但在某些生产环境里仍然有隐患。第一是递归深度数组规模 N 时递归深度约为 log₂N比如 1 亿个元素大约 27 层这倒不至于爆栈第二是函数调用开销在大数据量下依然可感知所以许多高性能实现会切换到自底向上的迭代版本。自底向上的思路是先把相邻的两个元素排序再把相邻的长度为 2 的有序块合并再合并长度为 4 的有序块依次翻倍直到整个数组有序。这里的启示是理解归并排序递归版是门槛真正用到极致往往是迭代版或改进版。后面讲工程场景时还会提到 TimSort 这种高级归并排序它就是基于这种自底向上的区间合并思路再叠加优化得来的。4. 复杂度与空间为什么归并排序稳定在 O(n log n)代价是什么4.1 时间复杂度的数学直觉一棵递归树归并排序的时间复杂度推导是几个经典排序里最直观的。设总时间 T(n)一次归并对规模为 n 的问题而言拆两部分各解2T(n/2)合并本身O(n)于是有递推式T(n) 2T(n/2) O(n)展开T(n) 2(2T(n/4) O(n/2)) O(n) 4T(n/4) 2O(n)以此类推到第 k 层时T(n) 2ᵏ T(n/2ᵏ) kO(n)当 n/2ᵏ 1 时k log₂n此时 T(1) 为常数所以总时间就是 O(n log n)。用递归树来看更直白每一层要做的是把当前所有子区间分别合并而所有子区间的长度加起来是 n所以每层的合并总代价是 O(n)树高 log₂n 层乘起来就是 O(n log n)。关键结论是无论输入是最好情况、最坏情况还是平均情况归并排序都是先拆到底再合并中间不存在跳过合并的捷径所以它永远都是 O(n log n)。这跟快排有本质差异——快排的最坏情况能退化成 O(n²)虽然平均也快但归并排序胜在不会翻车。4.2 空间复杂度 O(n)它是怎么吃掉内存的归并排序最被诟病的就是空间开销。每轮合并都要用临时数组存结果递归版在某一时刻需要 O(n) 的辅助空间所以总空间复杂度是 O(n)。那有没有办法做到原地归并理论上也有原地归并的算法但在数组中交换元素保持两段子序列有序操作成本极高实践中几乎没人用。用空间换稳定性和性能下限这件事在很多场景下是划算的。真正看重空间的场景通常会用链表来实现归并排序——链表做归并排序不需要额外的辅助数组只需要改指针指向空间复杂度能压到 O(1)。这里有个很现实的问题为什么 Java 的Arrays.sort()对基本类型数组用双轴快排对对象数组用 TimSort基本类型数组不在乎稳定性快排的空间开销小、常数低是更好的选择对象数组往往需要保持相等元素的相对顺序所以归并思路成了刚需。排序 API 的这个设计差异其实就是时间和空间、稳定性之间博弈的最好注脚。排序算法平均时间复杂度最坏时间复杂度额外空间稳定性冒泡排序O(n²)O(n²)O(1)稳定快速排序O(n log n)O(n²)O(log n)不稳定堆排序O(n log n)O(n log n)O(1)不稳定归并排序O(n log n)O(n log n)O(n)稳定这张表里最值得记的是如果你既要稳定的最坏复杂度又要稳定性归并排序几乎是唯一直接可用的答案。4.3 快排 vs 堆排 vs 归并工程场景里到底怎么选我在实际项目里看到不少同事一排序就Collections.sort()拉倒这也没问题但理解底层选择的逻辑还是有价值的。数据规模很小比如几十个元素插排效果最好常数极小归并反而因为开临时数组显得笨重。JDK 里的 TimSort 就对小数组用插入排序最后再用归并思想连接。数据基本有序原地快排类算法容易浪费在无效分区上而 TimSort 能识别天然的有序块用归并连接效率极高。内存充裕、要求稳定、数据量大直接归并排序或 TimSort。内存紧张堆排序的空间优势明显但它牺牲稳定性而且实际常数较大并不总是首选。5. 工程战场上的归并排序外部排序、多路归并与并行优化5.1 内存放不下的时候就是归并排序发光的时候我开头提到的 2GB 日志文件就是典型的外部排序场景。数据量超过内存容量时你不可能一次性把全部数据读进来排序常规的数组排序全都派不上用场。外部排序的思路可以概括成两句话分段排序把大文件切分成能够整体载入内存的若干块每块单独用内存排序算法排好再写回磁盘。每个有序块称为一个 run。多路归并把这些 run 通过归并的方式逐步合并成越来越大的有序文件最终得到全局有序的文件。第一步用快速排序或者归并排序都可以因为每块都放得进内存第二步就是归并排序的天下——它只需要在各 run 的头部保持一个小的缓冲区不断取最小元素完美契合磁盘顺序读取的特点。快排在这里反而不好使因为快排需要随机访问整个数据集而数据都在磁盘上随机访问的代价高到无法接受。从这个角度看归并排序不仅是排序算法更是一套让排序适应存储层级的工程方法论。5.2 从二路归并到 K 路归并当外部排序的数据规模上万二路归并是最简单的方案但在实际外部排序里往往 run 的数量会非常大。举个例子1TB 数据切成 100MB 一个 runrun 的总数就是 1 万个如果用两路归并每趟只能让 run 数量减半需要约 14 趟读写而如果用 100 路归并一趟就能把 1 万个 run 合并成 100 个再走一趟就完成磁盘 IO 总量大幅下降。多路归并的多路核心难点在于如何在 k 个 run 的头部元素中找到最小值。最朴素的做法是每选一个元素就把 k 个首元素全比较一遍这样一趟的复杂度是 O(k)k 越大开销越大。工程上更常用的方案是败者树它是堆的一种变体每次选出最小值只需要 O(log k) 的成本。这样即便 k 很大也能维持高效的归并。5.3 并行归并多核 CPU 时代的分治扩展归并排序的分本身就天然适合并行化。试想有 8 个 CPU 核心我可以把一个大数组均分为 8 段每个核独立排序一段然后再做多路归并。每一段的排序互相不依赖这是分治法带来的天然优势快排虽然也能并行但要处理分区间的关联麻烦得多。更细的并行优化还有两层一是像上面说的并行本地排序二是连最后的归并阶段也并行化——比如把目标区间再切小多个线程同时负责不同子区间的合并前提是每个子区间的元素来源必须从多路输入里正确分配这通常需要做二分查找来确定切分点。工程实践中很多大数据框架的排序阶段正是利用这个思路把归并和并行结合在一起的。5.4 你每天都在用的归并排序改良版TimSort如果觉得自己平时没直接写过归并排序那你就错了。Python 的sorted()、Java 的Arrays.sort(Object[])、Android 的Collections.sort()底层用的都是 TimSort。TimSort 的想法非常工程化先扫描数组把已经天然有序的子区间包括递减区间反转成递增识别出来称为 run。用插入排序把小 run 扩展到一定长度避免开太多的归并段。然后像自底向上的归并排序一样把相邻 run 按规则合并。这套设计充分利用了现实数据的部分有序性所以实际表现经常比纯归并排序和纯快排还要好。它的存在从侧面证明了一件事归并排序最值钱的地方不在教科书里而在它对数据模式的高度适应能力上。数据库的排序算子和 MapReduce 框架的 Shuffle 阶段同样充斥着外部归并排序的影子。所谓底层算法其实就在这些重量级系统的核心链路里每天运转着。把归并排序的分治思想消化掉再去看这些框架的源码实现你会发现一切都是相通的。最后再分享一个我面试时的个人习惯我会让候选人手写归并排序并追问为什么最后一定要拷贝回原数组在哪里才能判断已经有序。能答上后一个问题的候选人通常才是真懂归并排序——在right - left 1时数组天然有序根本不需要任何判断也没有提前退出的空间这正是归并排序稳定 O(n log n)的本质来源。希望这篇文章能帮你把这个算法从背代码变成看透设计实际用起来真的会顺畅很多。