★ FEATURED ARTICLE 如果只能选一个排序算法来讲清楚什么是分治思想我会选归并排序。它的时间复杂度稳定在 O(nlogn)无论数据本来是什么样表现都不会退化这是快排在极端情况下都比不了的。更重要的是归并排序不只是“一个排序算法”它的合并思路直接延伸出了外部排序、逆序对统计、链表排序等高阶玩法几乎是算法面试里最常被拿来深挖的知识点之一。这篇文章适合两类人一类是刚学完冒泡、选择、插入排序想系统理解分治排序的初学者另一类是面试前想把这套东西彻底讲明白、把变体真正搞懂的求职者。我会把思路、复杂度推导、手写代码、常见坑和优化方案全部拆开讲争取让你看完就能写出一份干净的实现也能把 O(nlogn) 这个复杂度说到别人点头。1. 先弄明白归并排序到底在“归并”什么1.1 分治三步走拆、排、合归并排序的英文叫 Merge Sort核心动作就两个归并和排序。但真正理解它之前得先接受一个看起来很“绕”的设定我们要把一个乱序数组变有序不直接对整个数组下手而是先把它切成两半把左半部分排好序、右半部分排好序最后再把两个有序半区合并成一个有序整体。这个过程就是典型的分治Divide and Conquer分解Divide、解决Conquer、合并Combine。具体到归并排序就是三步拆把数组从中间位置一分为二得到左右两个子数组。排递归地对左右两个子数组分别做归并排序直到子数组只剩一个元素。一个元素天然有序不用再排。合把两个已经各自有序的子数组合并成一个更大的有序数组。这也是为什么叫“二路归并”——每次合并的都是两个有序序列。你可以理解为两堆已经按从小到大排好的扑克牌现在要把它们合在一起还是有序的做法就是每次从两堆牌的顶部各取一张比较大小把更小的那一张放到结果堆里然后继续。“拆”这个动作看起来简单里面藏着一个关键细节拆分不是把数据复制成两个新数组而是用索引来“假装切开”。我们操作的是同一个数组只是通过 left、mid、right 三个下标把它的逻辑范围分成两段。这样做的好处是不用额外复制数据省内存也省时间。很多初学者第一次写归并排序时总想着把左半部分拷到一个新数组再拷右半部分最后再合并成一个新数组——这样也能跑通但完全没有必要代码还会变得很啰嗦。1.2 合并两个有序数组是整个算法的灵魂合并这一步可以说是归并排序真正的“技术含量”所在。前面那些拆分、递归本质上都是在为合并创造前提条件。如果给一个完全乱序的数组直接做合并是没有意义的——只有左右两半都已经有序合并过程才能在线性时间内完成任务。合并操作本身很短但边界条件特别容易写错。它的核心逻辑是用两个指针 i 和 j 分别指向左子数组和右子数组的开头比较 arr[i] 和 arr[j] 的大小把较小的元素放进一个临时数组然后让对应的指针往后移动一格。重复这个过程直到某一方的元素被取完再把另一方的剩余元素直接按顺序拷进临时数组。为什么剩余元素可以直接拷因为左右两个子数组在进入合并之前都已经是有序的所以在某一方耗尽之后另一方剩下的元素不仅有序而且全都比已经放入临时数组的元素大直接追加就不会有任何问题。合并完成之后还需要一步收尾动作把临时数组里的元素写回原数组的对应位置。这一步忘了做或者写回的位置搞错整个排序结果就是乱的。用生活里的场景来理解合并就像你把两列各自排好队的同学合并成一列更长的队一边的同学依次出队比较身高矮的先进新队列最后一边没人了另一边剩下的同学按顺序全部进入新队列——这时你还要让这支新队伍站回原来的教室位置才算真正完成合并。2. O(nlogn) 是怎么算出来的递归式与递归树2.1 从递归式 T(n) 2T(n/2) O(n) 说起归并排序的时间复杂度不能只靠“感觉说好像挺快”来糊弄得能推导出来。推导的起点是一个递归式。如果一个规模为 n 的问题被拆成两个规模为 n/2 的子问题分别解决它们各需要一个 T(n/2) 的时间在合并这两个子数组时要把所有 n 个元素都过一遍并放进临时数组所以合并成本是 O(n)。于是我们有T(n) 2T(n/2) O(n)这个式子读起来就是排序 n 个元素的时间等于排序左半边的时间加上排序右半边的时间再加上合并两边花费的线性时间。那递归的底在哪里当 n 1 时一个元素已经有序不需要做任何排序和合并操作所以 T(1) O(1)。有了递推式和终止条件就可以开始展开这个递归式一层层看它到底累加出了什么结果。2.2 用递归树和主定理交叉验证先拿递归树来展开。假设 n 8画一下递归的层次第 0 层整个数组长度为 8合并这一层的数据需要 O(8) 时间。第 1 层分成两个长度为 4 的子数组每个子数组合并需要 O(4)两个合起来还是 O(8)。第 2 层分成四个长度为 2 的子数组每个合并需要 O(2)四个合起来还是 O(8)。第 3 层分成八个长度为 1 的子数组每个合并需要 O(1)八个合起来还是 O(8)。看出规律没有每一层的合并总代价都是 O(n)因为不管这一层有多少个子问题它们的规模加起来正好就是 n。而递归树一共有多少层每次规模减半从 n 减到 1需要 log2(n) 次拆分所以层数是 O(logn)。层数乘以每层的代价就得到了总复杂度T(n) O(logn) × O(n) O(nlogn)这个推导很直观也不依赖任何公式。如果你想用更规范的工具交叉验证可以上主定理Master Theorem。对于 T(n) aT(n/b) f(n)这里 a 2b 2f(n) O(n)那么 log2(2) 1f(n) 的阶正好是 n^1落入主定理的第二种情况直接得出 T(n) O(nlogn)。两个方法结论一致说明这个结果非常可信。2.3 为什么归并排序的最好、最坏、平均都是 O(nlogn)这一点是归并排序区别于快排的重要特征。快排在最坏情况下会退化到 O(n^2)因为如果每次选的基准都不巧分区会极端不均匀一边总是空的一边总是满的。但归并排序不会。归并排序的分裂永远是从中间一分为二跟数据的初始顺序没有关系。不管数组已经完全有序、完全逆序还是乱序到离谱拆分路径都一样递归树的层数都一样每层的合并代价也都是 O(n)。所以它的最好、最坏、平均时间复杂度稳定地保持在 O(nlogn)没有任何输入能把它拖下水。这种“输入不敏感”的特性在实践中意味着性能可预期。不需要担心某批数据恰好踩中退化场景。空间复杂度也要单独说清楚。归并排序不是原地排序因为合并阶段需要一块额外的临时数组大小跟待排序区间一致最大时是 n所以额外空间是 O(n)。递归调用本身还会占用系统栈栈的深度等于递归树的层数 O(logn)。把临时数组和调用栈加起来总体额外空间是 O(n logn)渐进意义上就是 O(n)。这也是归并排序经常被拿来和快排对比的一个点快排的额外空间平均是 O(logn)归并是 O(n)内存敏感的场景下归并就比较吃亏。3. 手把手写一个干净的归并排序3.1 一份可以直接跑的 JavaScript 实现直接上代码。我用 JavaScript 写因为它在算法面试和前端场景里覆盖很广而且又没有真正的“数组切片排序”这种系统函数来干扰思路。各位用 Python、Java 的也能看懂逻辑完全一致。function mergeSort(arr, left 0, right arr.length - 1) { if (left right) { return; } const mid (left right) 1; mergeSort(arr, left, mid); mergeSort(arr, mid 1, right); merge(arr, left, mid, right); } function merge(arr, left, mid, right) { const temp new Array(right - left 1); let i left; let j mid 1; let 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 (let m 0; m temp.length; m) { arr[left m] temp[m]; } }这段代码是标准的二路归并。注意几个细节mid 用(left right) 1计算等于Math.floor((left right) / 2)但写法更简洁。递归终止条件是left right等于说区间里只有一个元素甚至没有元素时就不动了。合并时临时数组的长度是right - left 1也就是当前区间的元素个数。两个 while 循环分别处理“某一方先走完”的情况最后再把临时数组内容从left开始逐个写回原数组。很多人写错的就是最后这一步写回时用arr[m] temp[m]而temp的下标是从 0 开始的原数组的位置却是从left开始的不对齐就直接把排序结果写飞到别的位置上。3.2 关键边界与稳定性细节写归并排序最常见的错误集中在几个边界上我列一下实测容易翻车的地方。第一空数组和单元素数组。mergeSort([])执行时left 0right -1触发left right直接返回没问题。但如果你的递归终止条件写的是left right空数组就会出问题所以写大于等于更稳妥。第二mid 的计算。不要写成(left right) / 2然后直接当索引用如果结果是浮点数数组访问会得到 undefined合并时会莫名报错或排错序。稳妥做法是取整 1或者Math.floor都可以。第三稳定性。归并排序天然是稳定的关键就在这一句if (arr[i] arr[j]) {注意是小于等于不是小于。如果写成小于当左右两边的元素相等时我们会先把右边那个放进临时数组而右边元素原本在整体顺序中位于左边元素之后这会破坏相同元素的相对位置稳定性就丢了。虽然对于纯数字数组来说稳定性好像无所谓但对按多个字段排序的对象数组很有意义。比如先按姓名排好序再按年龄做稳定排序年龄相同的还是要保持第一次排序后的相对顺序这时候稳定排序就很重要了。第四辅助空间的分配。上面这段代码每次 merge 都new一个数组对演示没问题但数据量一大GC 会很心疼。后面第 4 章我会说怎么优化。3.3 面试常见变形返回逆序对数量归并排序最有名的一个变体是计算逆序对。所谓逆序对就是数组中一对索引 i j但 arr[i] arr[j] 的元素对。比如[3, 1, 2]就有两对逆序对(3,1) 和 (3,2)。最朴素的做法是双重循环O(n^2)。但用归并排序可以在合并阶段顺便数出来复杂度降到 O(nlogn)。原理是这样的当我们在 merge 时发现arr[i] arr[j]说明从左半区当前位置 i 到左半区末尾 mid 的所有元素都比 arr[j] 大而且它们的索引都在 j 之前所以一共构成了mid - i 1个逆序对。let count 0; function mergeSortCount(arr, left 0, right arr.length - 1) { if (left right) { return; } const mid (left right) 1; mergeSortCount(arr, left, mid); mergeSortCount(arr, mid 1, right); mergeCount(arr, left, mid, right); } function mergeCount(arr, left, mid, right) { const temp new Array(right - left 1); let i left; let j mid 1; let k 0; while (i mid j right) { if (arr[i] arr[j]) { temp[k] arr[i]; } else { count mid - i 1; temp[k] arr[j]; } } while (i mid) { temp[k] arr[i]; } while (j right) { temp[k] arr[j]; } for (let m 0; m temp.length; m) { arr[left m] temp[m]; } }每次递归调用都会往全局 count 里累加最终就得到了整个数组的逆序对总数。这个题在很多算法面试里以各种包装出现本质上考的就是对归并合并过程的理解——你只有真正明白右半区某个元素能被左半区哪些元素“碾压”才能写出这行计数逻辑。4. 归并排序的三个实用优化4.1 小数组切到插入排序归并排序的递归开销不小。每次函数调用都要保存上下文、压栈、返回当子数组长度很小比如只有 4 个、8 个元素时递归调用的成本甚至可能高过直接做一次简单插入排序的成本。所以工程实践里普遍的做法是设定一个阈值子数组长度小于等于它时放弃继续递归改用插入排序。这个阈值没有绝对标准我习惯取 10 到 16。在递归函数开头加一句if (right - left 10) { for (let i left 1; i right; i) { const cur arr[i]; let j i - 1; while (j left arr[j] cur) { arr[j 1] arr[j]; j--; } arr[j 1] cur; } return; }插入排序在几乎有序的小数组上表现极好而且本身是稳定排序不会破坏归并排序的稳定性。实测下来对 10 万量级随机数组这个优化能带来肉眼可见的提升因为少了几万次递归调用和临时数组创建。4.2 复用辅助数组别让 GC 背锅原始实现里每次 merge 都创建一个新数组。递归到叶子附近时合并操作非常频繁短时间会创建大量小数组垃圾回收的压力会变得很大。优化思路很朴素提前一次性分配一个和原数组等长的辅助数组每次合并都用同一块内存。举个例子function mergeSort(arr) { const helper new Array(arr.length); sort(arr, 0, arr.length - 1, helper); } function sort(arr, left, right, helper) { if (left right) return; const mid (left right) 1; sort(arr, left, mid, helper); sort(arr, mid 1, right, helper); merge(arr, left, mid, right, helper); } function merge(arr, left, mid, right, helper) { for (let i left; i right; i) { helper[i] arr[i]; } let i left; let j mid 1; let k left; while (i mid j right) { if (helper[i] helper[j]) { arr[k] helper[i]; } else { arr[k] helper[j]; } } while (i mid) arr[k] helper[i]; while (j right) arr[k] helper[j]; }这个版本的思路是从原数组复制到辅助数组再从辅助数组合并回原数组省去了每层新建、拷贝、销毁临时数组的往返操作。对大规模排序来说内存分配次数从 O(nlogn) 级别的多次变成了 1 次收益非常明显。4.3 局部有序提前返回归并排序对输入不敏感但我们可以给它加一个敏感的判断如果左右两个子数组合并之前就已经天然有序那就不合并了。判断条件很简单看左半区最后一个元素是否小于等于右半区第一个元素if (arr[mid] arr[mid 1]) { return; }如果成立说明整个区间的最大值在左半区末尾最小值在右半区开头那左右两半拼起来已经整体有序合并纯属浪费。这个优化在数据接近有序时效果极其明显能让归并排序在“几乎有序”的数组上近乎线性地完成。虽然算法的最坏复杂度不变但实际场景中它的平均表现会有实打实的提升。要注意的是这三个优化可以同时叠加互不冲突。工程上这么实现的归并排序无论是稳定性、内存分配还是实际耗时都已经非常接近标准库排序的表现。5. 绕不开的变体自底向上、链表归并与外部排序5.1 自底向上归并递归栈深度可控前面讲的都是递归版本逻辑清晰但依赖系统调用栈。自底向上的非递归写法是另一条路线不拆分而是先让相邻的每 1 个元素为一组两两归并得到长度为 2 的有序块再让相邻的每 2 个元素为一组两两归并得到长度为 4 的有序块以此类推直到整个数组有序。function mergeSortBottomUp(arr) { const n arr.length; const helper new Array(n); for (let size 1; size n; size * 2) { for (let left 0; left n - size; left 2 * size) { const mid left size - 1; const right Math.min(left 2 * size - 1, n - 1); merge(arr, left, mid, right, helper); } } }合并函数可以复用上一节的辅助数组版本。这个写法的好处是彻底摆脱递归深度限制而且代码的执行路径非常直白。坏处是处理数组最后剩下那一截不完整块时边界算起来要更小心Math.min的钳位不能漏。5.2 链表归并空间复杂度可以做到 O(1)数组归并需要 O(n) 的额外空间是因为合并时需要临时存数据。但链表不是连续内存合并两个有序链表只需要改指针不需要任何额外数组。所以链表上的归并排序额外空间只取决于递归栈深度也就是 O(logn)如果再用自底向上的方式额外空间甚至可以压到 O(1)。链表归并的思路是用快慢指针找到链表的中点快指针每次走两步慢指针每次走一步快指针到达末尾时慢指针正好在中点。然后递归地对前后两段分别排序最后用标准的两个有序链表合并过程把它们串起来。合并两个有序链表时谁的头节点小谁就先进入结果链然后更新对应指针。这个操作非常干净也是因为链表天然适合“归并”这种线性操作。5.3 外部排序归并思想的工业级应用归并排序最大的舞台其实不在内存里而在磁盘上。当数据量超过内存容量时把所有数据一次性读进内存排序是不可能的。外部排序的做法是把大文件切分成多个能够完整读入内存的小块每个小块分别排序后写回磁盘形成若干有序段然后再把这些有序段做多路归并逐一比较各段开头的元素把最小的依次写入最终文件。整个过程的核心就是归并排序的合并思路。多路归并时通常用堆来优化比较过程从 K 个有序段中选出最小元素不需要每轮比较 K 次而是维护一个大小为 K 的最小堆每次取出堆顶再从所属的段中补入下一个元素复杂度从 O(K) 降到 O(logK)。这个技术在数据库、搜索引擎、日志处理这些领域是真实每天都在跑的。你去面试后端方向聊到海量数据排序大概率会扯到这里。能说出“外部排序本质就是归并排序 堆优化”面试官会知道你确实懂原理而不只是背代码。6. 常见问题与排查技巧速查表6.1 高频踩坑点对照表现象可能原因解决方案排序结果完全没变merge 里没有写回原数组或写回起始位置不是 left检查写回循环arr[left m] temp[m]排序结果部分错乱mid 或 right 边界算错确认mid (left right) 1j mid 1循环条件是i mid j right大数组排序时内存猛涨每次 merge 都 new 新数组预分配一个全局辅助数组递归深度异常 / 栈溢出数组超大且递归层数深改用自底向上非递归版本相同元素的相对顺序变了合并时用而不是改成运行时间比预期慢很多缺少小数组阈值优化递归太深或辅助数组频繁创建加插入排序阈值 复用辅助数组6.2 实操心得这样调试效率最高写归并排序时我最推荐的调试方式是“小数组手推”。拿[4, 3, 2, 1]这种 4 个元素的逆序数组在纸上画递归树把每一步的 left、mid、right 和 merge 后的数组状态写出来。跑一遍程序对比基本半小时内就能把所有边界问题暴露完。还有一个实用技巧在 merge 开始时加一行日志把left, mid, right和合并前的数组打出来能快速定位到底是拆分错了还是合并顺序错了。工程里排查数据管道问题也是这个思路——先看输入再看出输中间逻辑用日志锚定。另外面试时如果写归并排序我建议先把思路口头说清楚告诉面试官这是分治先递归后合并然后写一个 merge 函数和一个递归主函数结构比直接堆代码要清楚得多。写完主动提一句“这里用是为了保持稳定性”会显得你对细节有掌控力。别小看这些表现它往往是面试官决定要不要深挖你的关键信号。我个人在实际使用里的体会是手写归并排序的机会虽然不多但理解这套分治框架非常划算。它的“局部有序到整体有序”的思路在合并接口返回的数据、整合多个有序列表、处理增量数据归并这些业务场景里都直接能用。把归并排序当成一个可以迁移的思维工具来看待收获远大于“会背一个排序算法”。最后再分享一个小技巧如果你在实现时需要临时验证排序是否正确不要只测随机数组务必测一下全部相等的[5,5,5,5,5]和完全逆序的[5,4,3,2,1]。前者能测出稳定性写没写对后者能测出递归边界和合并逻辑是否坚固。这两个用例过了归并排序基本就算写得扎实了。
阅读完成 · 觉得有帮助？
