归并排序面试被问懵之后我把 LeetCode 上所有相关题一次啃透了先交代一下背景。去年集中刷 LeetCode 的时候我一度很排斥归并排序——总觉得直接调sort()不就完了手写这玩意儿干嘛直到某次模拟面试被问到“如何统计数组中的逆序对”我脑子里闪过一堆思路最后连一个能跑的归并代码都没写利索。面试官没说什么但那个微笑我记到现在。后来我把归并排序在 LeetCode 上的经典题全部梳理了一遍从模板到变体、从递归到迭代、从排序到计数摸透了之后才发现归并排序根本不只是一个“排序算法”它是一套极其通用的分治框架。排序只是它的表面能力利用合并过程的顺序信息去解决计数、统计、区间类问题才是它真正的价值所在。这篇文章把我踩过的坑、总结出的模板、以及几种高频题目的完整解法全部整理出来希望对正在刷题的你有用。1. 归并排序在面试题里的真实地位1.1 面试官到底在考什么先说一个判断如果你面试时只被要求“手写归并排序”那多半是热身题。真正的考点从来不是你能不能写出归并那两行合并逻辑而是以下几个方面是否理解分治的递归展开过程能否徒手画出递归树是否知道归并排序是稳定排序且稳定性的来源在哪里能否从“合并两个有序数组”的过程里联想到逆序对、区间和统计等衍生问题是否能在递归和迭代两种实现之间自由切换并说清各自的优劣势。换句话说归并排序是面试官探测你算法基本功的探针。你只背模板就只答对了第一问真正理解了归并过程的结构化特征后面几个问题才能稳。1.2 归并排序和快速排序的边界感很多初学者会把归并排序和快速排序搞混因为两者都是“分治”。但又有一个关键区别快速排序是“先分组再处理”分组的过程本身就带着 partition 的排序动作属于原址排序归并排序则是“先拆到底再合并”真正做事的是合并阶段而且需要额外空间。这个区别直接决定了你会遇到什么问题快排难在 partition 的边界处理和退化情况比如有序数组归并难在内存开销、递归栈深度、以及合并时指针越界。如果你用归并排序刷题空间复杂度 O(n) 一般是可接受的但你要是拿它去处理一个上亿的数据集就得考虑外部排序的思路了。后面我会专门讲这个扩展方向。2. 归并排序核心原理分治框架与复杂度推导2.1 分治三步走归并排序的框架在任何语言里都是同一套逻辑可以抽象成三步分解Divide把数组从中间切成两半得到左子数组和右子数组解决Conquer递归地对两个子数组分别排序合并Combine把两个已经有序的子数组合并成一个大的有序数组。整个过程终止条件是子数组长度为 0 或 1此时天然有序直接返回。听起来非常简单但真正写代码的时候绝大部分 bug 都出在第 3 步的合并边界上后面我会专门列出来。2.2 时间复杂度推导为什么是 O(n log n)时间复杂度是数学推导出来的值得自己手推一遍而不是死记结论。假设问题规模为 n每一步把数组分成两半所以递归树的深度是 log₂n 层每一层上所有合并操作加起来都要扫描 n 个元素。所以总复杂度是每层的工作量 n 乘以层数 log n即 O(n log n)。这里有两个容易忽略的点归并排序的时间复杂度与输入数据是否有序无关。即使数组已经全部有序它依然要逐层拆分、逐层合并所以最好、最坏、平均都是 O(n log n)。这一点是它和快速排序最大的差异快排有序退化到 O(n²)归并不会。如果你在递归里每次都用slice之类的语法复制子数组你会多出 O(n log n) 的复制开销。刷 LeetCode 时数据量一上来就容易 TLE 或超内存。正确做法是只开一个临时数组全程复用通过索引范围描述子数组不做数组物理切割。2.3 稳定性来源与空间复杂度稳定性指的是值相同的元素排序后相对位置不变。归并排序是稳定排序稳定性从哪来的就在合并时那个的等号上。当前半段元素等于后半段元素时我们优先取前半段这样相等的元素保持了原来的相对次序。所以提醒一句如果你在合并代码里把误写成稳定性就被破坏了。在纯排序场景可能看不大出来但在“按多个字段排序”或“保持原始序号”等问题里这个细节直接决定答案对不对。空间复杂度方面归并排序需要一个长度为 n 的临时数组所以空间复杂度是 O(n)。递归调用本身还要占用栈空间深度 O(log n)但 O(n) 的临时数组是大头。LeetCode 上归并排序相关题目的内存限制一般都能过但如果你同时复制了多个数组就会翻车。3. 两种实现模板递归写法与迭代写法3.1 递归模板以 Java 为例LeetCode 刷题最常用的还是递归写法逻辑清晰面试时也好讲。下面这段是我反复精简后的模板class Solution { public int[] sortArray(int[] nums) { mergeSort(nums, 0, nums.length - 1, new int[nums.length]); return nums; } private void mergeSort(int[] nums, int left, int right, int[] temp) { if (left right) return; int mid left (right - left) / 2; mergeSort(nums, left, mid, temp); mergeSort(nums, mid 1, right, temp); merge(nums, left, mid, right, temp); } private void merge(int[] nums, int left, int mid, int right, int[] temp) { int i left; int j mid 1; int k 0; while (i mid j right) { if (nums[i] nums[j]) { temp[k] nums[i]; } else { temp[k] nums[j]; } } while (i mid) { temp[k] nums[i]; } while (j right) { temp[k] nums[j]; } for (int p 0; p k; p) { nums[left p] temp[p]; } } }几个关键点left (right - left) / 2而不是(left right) / 2是为了防止 left right 溢出。这种细节在面试中会加分但归根结底是防 bug 的实用习惯。temp数组在sortArray里一次性创建传递给递归过程复用避免每层递归都 new 数组。合并结束后回填原数组时要从left p的位置开始写不是从 0 开始写。初次手写归并的人经常在这里犯错导致每次合并后前半段数据错乱。3.2 迭代模板自底向上的归并递归版本虽然直观但面试官有时会追问“你能不能写非递归版本”因为递归有栈深度风险某些场景下比如处理超长数组迭代版本更稳。自底向上的思路是先把数组看成 n 个长度为 1 的有序段然后每相邻两个段合并一次得到长度为 2 的有序段接着两两合并得到长度为 4 的有序段……不断翻倍直到整个数组合并完成。class Solution { public int[] sortArray(int[] nums) { int n nums.length; int[] temp new int[n]; for (int len 1; len n; len * 2) { for (int left 0; left n - len; left 2 * len) { int mid left len - 1; int right Math.min(left 2 * len - 1, n - 1); merge(nums, left, mid, right, temp); } } return nums; } private void merge(int[] nums, int left, int mid, int right, int[] temp) { int i left; int j mid 1; int k 0; while (i mid j right) { if (nums[i] nums[j]) { temp[k] nums[i]; } else { temp[k] nums[j]; } } while (i mid) { temp[k] nums[i]; } while (j right) { temp[k] nums[j]; } for (int p 0; p k; p) { nums[left p] temp[p]; } } }注意迭代版本的几个边界外层循环len表示当前有序段长度每次翻倍。内层循环left从 0 开始步长为2 * len每次处理两个相邻长度为len的段。mid left len - 1不能漏掉- 1否则区间会多出一个元素。最后一个段的right可能超过数组末尾必须用Math.min(..., n - 1)截断否则越界。迭代版本的空间复杂度同样是 O(n)但它避免了递归栈适合在嵌入式或资源受限环境里排序。LeetCode 刷题时用递归版本就足够不过迭代写法能体现你的理解深度。3.3 两种写法的对比与选择维度递归版本迭代版本代码可读性高逻辑贴合分治思想中边界条件较绕栈风险深度 O(log n)一般没问题无递归栈开销实现难度低中LeetCode 使用推荐代码简洁备选体现进阶能力4. LeetCode 实战场景拆解4.1 排序数组第 912 题这是归并排序最直接的 LeetCode 场景。题面很简单给你一个整数数组要求升序排序。很多人第一反应是用Arrays.sort()但如果你刷这道题的目的是练排序算法直接调 API 就白费了。我的建议是用这道题作为归并排序模板的验证场。把上面的递归模板贴进去直接提交能过就说明你的基础实现没问题。注意题目的取值范围比较大如果代码里出现 O(n²) 的意外复杂度就会超时而归并排序的 O(n log n) 是稳定可过的。4.2 数组中的逆序对剑指 Offer 第 51 题这道题是归并排序最常见的面试变体也是我认为最值得深挖的一道题。题面是在数组中的两个数字如果前面一个数字大于后面的数字则这两个数字组成一个逆序对。输入一个数组求逆序对总数。最暴力的解法是两层循环O(n²)。但当 n 达到 50000 甚至更大暴力必挂。归并排序解法是基于一个核心观察合并两个有序数组时如果右半段的当前元素小于左半段的当前元素那么左半段从当前元素到结尾的所有元素都和右半段的这个元素构成逆序对。道理不复杂因为左半段内部是有序的当前元素是左半段剩余部分的最小值。如果这个最小值都大于右半段当前的元素那么左半段剩余的所有元素都大于它所以一次性可以累加mid - i 1个逆序对。这就是归并过程里“多算一步统计”的思想。参考代码如下class Solution { private long count 0; public int reversePairs(int[] nums) { mergeSort(nums, 0, nums.length - 1, new int[nums.length]); return (int) count; } private void mergeSort(int[] nums, int left, int right, int[] temp) { if (left right) return; int mid left (right - left) / 2; mergeSort(nums, left, mid, temp); mergeSort(nums, mid 1, right, temp); merge(nums, left, mid, right, temp); } private void merge(int[] nums, int left, int mid, int right, int[] temp) { int i left; int j mid 1; int k 0; while (i mid j right) { if (nums[i] nums[j]) { temp[k] nums[i]; } else { count mid - i 1; temp[k] nums[j]; } } while (i mid) { temp[k] nums[i]; } while (j right) { temp[k] nums[j]; } for (int p 0; p k; p) { nums[left p] temp[p]; } } }为什么count用long因为逆序对数量最坏情况是数组完全逆序比如[n, n-1, ..., 1]逆序对总数是 n*(n-1)/2n 稍微大一点就会超出 int 范围。LeetCode 题目本身不要求取模所以要用long存结果最后转回int。这道题的价值在于它展示了归并排序的合并过程不仅是“排序”而是在“比较两个有序序列”的时候可以顺手完成某种统计。这种思想可以迁移到很多“区间统计”类问题。4.3 排序链表第 148 题链表上的归并排序是另一个高频考点。普通数组排序可以直接按下标切分链表不行需要利用快慢指针找到中点然后递归排序前后两段最后合并两个有序链表。链表归并与数组归并最大的不同是不需要额外 O(n) 空间严格来说不需要临时数组只需要调整指针。所以链表归并排序的空间复杂度是 O(log n)来自递归栈。核心代码如下class Solution { public ListNode sortList(ListNode head) { if (head null || head.next null) return head; ListNode slow head; ListNode fast head.next; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; } ListNode rightHead slow.next; slow.next null; ListNode left sortList(head); ListNode right sortList(rightHead); return mergeTwoLists(left, right); } private ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummy new ListNode(0); ListNode cur dummy; while (l1 ! null l2 ! null) { if (l1.val l2.val) { cur.next l1; l1 l1.next; } else { cur.next l2; l2 l2.next; } cur cur.next; } if (l1 ! null) cur.next l1; if (l2 ! null) cur.next l2; return dummy.next; } }链表归并要注意两个细节找中点时fast初始化为head.next这样当链表长度为 2 时slow会落在第一个节点上保证左右两段都非空。如果fast head长度为 2 时slow会落在第二个节点left为空递归就永远无法结束。slow.next null这一步不能省它负责切断左右两段否则递归排序右半段时还是能够通过next指针访问到左半段的节点。链表归并排序的时间复杂度也是 O(n log n)虽然快慢指针找中点每次要扫描 O(n/2)但整体递归树的每层总工作量仍然是 O(n)所以总复杂度不变。4.4 区间和计数类问题第 327 题归并排序还有一种更隐蔽的应用区间和统计。以第 327 题“区间和的个数”为例题面是给定数组要求计算区间和在 [lower, upper] 范围内的个数。暴力做法是枚举所有区间O(n²)超时。用归并排序怎么优化核心思路是计算前缀和数组prefixSum区间[i, j]的和就是prefixSum[j] - prefixSum[i - 1]问题转化为在前缀和数组中有多少对(i, j)满足lower prefixSum[j] - prefixSum[i] upper归并排序在合并左右两个有序前缀和子数组时可以顺带统计满足条件的数对数量。这一步统计的核心是由于左右两个子数组都是有序的对于每个左段元素右段中满足区间条件的元素会落在一个连续的范围内可以用两个指针l和r维护这个范围的边界。具体逻辑比较精巧不是简单的“逆序对 1”能概括的建议先搞懂逆序对版本再来看这题。这类问题的意义在于它揭示了归并排序的合并阶段可以承载“两个有序序列之间的配对计数”这一通用操作。逆序对是基础版区间和计数是进阶版。一旦你理解了这层抽象遇到其他“有序配对统计”的问题都可以尝试用归并框架去套。5. 常见问题与排查技巧5.1 越界与死循环问题归并排序里最常见的崩溃就是数组越界。出现越界时优先检查这几个位置mid left (right - left) / 2是否正确递归终止条件left right是否写成了left right迭代版本中right是否用Math.min截断合并回填时是否从left偏移开始写。死循环则多半是因为边界计算错误导致子区间没有缩小常见于链表找中点时fast初始化不对或者递归时切分区间重叠。5.2 合并阶段的三个经典坑坑错误写法示例后果正确写法等号丢失if (nums[i] nums[j])破坏稳定性if (nums[i] nums[j])回填位置错误nums[p] temp[p]原数组前半段被覆盖nums[left p] temp[p]未处理剩余元素合并只写 while 主循环丢失后半段元素补两个 while 处理剩余第一个坑前面已经解释过。第二个坑我刚才也提到了这里再强调一次合并完后temp数组里有序元素是从 0 开始的但目标位置不是从 0 开始必须从left开始回填。第三个坑很容易理解但特别容易漏当一边数组耗尽时另一边一定还有剩余元素要把它们全部拷贝过去否则结果就缺元素。5.3 调试归并的实操方法论我实测下来最有效的调试手段是用小型随机数组加断言。具体操作是写一个测试函数对随机生成的数组分别用Arrays.sort()和你的归并排序跑一遍然后比对结果。这样能快速暴露合并和回填的问题。如果结果不对再加一个“打印递归过程”开关。在merge方法开头打印left、mid、right和当前数组内容肉眼追踪一遍合并过程基本就能定位是切分错了还是合并错了。注意调试时不要直接拿 LeetCode 的大数据用例硬跑那样输出太多反而看不清问题。数据量固定在 8 到 16 个元素加上随机打乱打印出每一步的状态很快就能发现问题。6. 归并排序的扩展与现实应用归并排序在编程面试之外还有很多现实应用场景理解这些能帮你在面试里回答“为什么学这个”的问题也能让你对算法有更整体的认识。最经典的是外部排序。想象一个场景内存只有 2GB但磁盘上有一个 20GB 的文件需要排序。你不可能一次性把所有数据加载进内存这时就用到了归并排序的分治思想。先把大文件切分成若干个小块每块都能加载进内存排序排序后写回磁盘然后再多路归并这些有序块最终生成一个完整的有序文件。归并排序支持“分段处理、逐步合并”的特性让它成为外部排序的地基。另一个场景是数据库的多路归并。数据库执行排序操作时如果排序数据超过内存缓冲就会使用类似外部排序的方案。归并排序的稳定性和可控性使它成为数据库内部实现排序算子的重要工具。还有 MapReduce 框架中的 Shuffle 阶段Map 端的输出需要按键排序后再传递给 Reduce 端。这个排序过程在数据量巨大时也是通过归并排序的分段合并思想来实现的。很多分布式计算引擎里实际上都是先在每个分区内排序再对所有分区做多路归并。这些场景本质上都是同一个模式数据太大放不进内存或者数据分布在多个节点无法一次性全局排序那就先局部有序再逐层合并。归并排序“只需要比较两个有序序列”的局部特性让它在这种场景下几乎是唯一的选择。所以即使你在 LeetCode 上不会遇到“20GB 文件排序”这种题理解归并排序的合并机制对你理解底层系统的设计也很有帮助。面试官如果问到“归并排序还有哪些应用”你能说出外部排序和数据库多路归并往往会成为加分项。7. 一些实战心得最后分享几个刷题过程中总结出来的经验算是给读者的额外福利。第一模板要固化但不要死背。归并排序的模板并不长关键在于每次写的时候心里要清楚每一步在做什么而不是照抄。我建议你至少手写五遍每一遍都慢下来把递归树画一遍把合并过程用笔记模拟一遍。等你闭上眼睛能完整默写出递归和迭代两个版本再去做变体题就顺了。第二变体题的突破口在于“合并时能做什么计算”。归并排序的框架里merge阶段比较两段有序数组的过程天然暴露了元素之间的相对顺序关系。逆序对、区间和计数都是利用合并时的顺序信息避免重复扫描。遇到这类问题先问自己能不能通过归并的合并阶段来统计答案如果可以大概率就是归并的变体。第三注意与其它排序的搭配使用。在排序链表这题中归并排序看起来就是个自然的答案因为链表的随机访问成本高不适合快排而堆排序又需要额外结构。实际面试中如果问题限定空间复杂度 O(1)你就要想想链表归并是否能用迭代 指针技巧把递归栈也省掉这又是一个进阶话题。说实话归并排序的代码量不大但涉及的思想密度很高。从朴素的排序到逆序对统计再到区间和计数再到外部排序一条线走下来你会发现自己对分治的理解上了一个台阶。刷题不是目的能在一道题里看到一类问题、一个框架、一套可迁移的方法论才算真正有所收获。
