归并排序在力扣题里被严重低估了。很多人接触归并排序是在《算法导论》或者数据结构课上背完模板就扔了觉得这玩意儿不就是分治 合并嘛面试考得少、写起来又长性价比不高。但实际上归并排序在 LeetCode 上的出场频率远比想象中高而且它从来不是以排序本身的面目出现的——更多时候它是藏在逆序对、区间和、链表排序这类题背后的那个核心框架。你一旦理解了归并排序的分治统计特性很多 Hard 题会突然变得顺畅起来。这篇文章我想从归并排序的底层逻辑讲起再用三道力扣原题把它的三个典型考法拆开揉碎最后整理一批我在刷题和面试中反复踩过的坑。无论你是刚开始刷题的新手还是准备面试想查漏补缺这篇内容都值得你花半小时细看。1. 归并排序的核心不是排序而是分治统计1.1 归并排序的本质是后序遍历先说一个很多人没想透的点归并排序的过程本质上是一棵二叉树的后序遍历。你看它的递归结构先把数组从中间切开分成左右两半递归处理左半边递归处理右半边最后把两个有序数组合并成一个。这个先左、再右、最后合并的顺序和后序遍历一模一样。而这个结构带来的最大好处是当你在 merge 阶段处理数据时你能同时拿到左右两部分的有序结果。这意味着你可以在这时候做跨区间的统计而不仅仅是排序。什么是跨区间的统计举个例子统计数组中逆序对的数量。如果我想数出所有满足i j 且 nums[i] nums[j]的组合常规暴力法是两两比较O(n²)。但如果数组左右两半都已经有序我在合并时就能快速数出左边有多少个元素大于右边某个元素——因为左边是有序的一旦发现nums[i] nums[j]那么从i到mid的所有元素都大于nums[j]一次性就能数出一大片。这就是归并排序的真正价值它用 O(n log n) 的代价顺带解决了那些需要用两个元素间关系来定义的统计问题。排序只是表面分治统计才是内在。1.2 稳定排序与辅助数组的细节归并排序是稳定排序这是个很关键的属性。稳定意味着相等的元素在排序后保持原有相对顺序。这个特性在按照某个键排序同时保持另一个键的顺序这类的题目里特别有用力扣上有些题会隐式地依赖这一点。归并排序的时间复杂度是稳定的 O(n log n)无论数组原本有序还是完全无序它都执行同样的递归拆分与合并。这一点和快速排序不同快排最坏会退化到 O(n²)而归并排序不存在这个问题——代价是需要 O(n) 的额外空间。力扣上不需要你现场手写一个省空间的归并实现用辅助数组是常规做法。细节上归并排序通常写左闭右开区间[left, right)。这样写有几个好处两个子区间分别是[left, mid)和[mid, right)两者之间天然无缝衔接递归结束时left 1 right代码里不容易出现 off-by-one 错误。这个区间写法我会在后面的代码里保持一致。2. 三类归并排序力扣题的高频考法2.1 排序本身合并两个有序数组力扣第 88 题合并两个有序数组是最直接的归并排序应用。题目给两个有序数组要求把第二个数组合并进第一个数组第一个数组预留了足够的空间。这题的考点有两个一是双指针合并的技巧二是从后往前覆盖的思路。如果从前往后合并nums1 的元素可能会被覆盖掉从后往前因为两个数组都是有序的较大的元素一定放在后面所以可以安全地倒着填。def merge(nums1, m, nums2, n): i, j m - 1, n - 1 k m n - 1 while j 0: if i 0 and nums1[i] nums2[j]: nums1[k] nums1[i] i - 1 else: nums1[k] nums2[j] j - 1 k - 1注意循环终止条件是j 0因为 nums2 是必须全塞进去的而 nums1 剩下的元素本来就在正确位置上。这段代码其实就是归并排序中 merge 函数的简化版——只处理两个有序数组不需要递归分治。这题虽然简单但它是后面所有归并题目的地基。如果这题的双指针逻辑不熟建议先反复写几遍直到闭着眼能写对为止。2.2 链表场景排序链表力扣第 148 题排序链表要求对链表排序时间复杂度 O(n log n)空间复杂度 O(1)。链表不像数组不能随机访问所以很多排序算法在链表上施展不开而归并排序天然适配链表——它只需要递归地把链表拆成两半然后合并两条有序链表即可。链表版本和数组版本的最大区别在于找中点。数组版直接mid (left right) // 2链表版需要用快慢指针。快指针每次走两步慢指针每次走一步快指针到末尾时慢指针正好在中点。def sortList(head): if not head or not head.next: return head slow, fast head, head.next while fast and fast.next: slow slow.next fast fast.next.next mid slow.next slow.next None l1 sortList(head) l2 sortList(mid) return mergeTwoLists(l1, l2)这里有个细节初始化时fast head.next而不是fast head。如果用fast head对于长度为 2 的链表快慢指针会同时停在中点偏后的位置导致拆分不正确。用fast head.next可以让慢指针停在左半部分的最后一个节点方便切断链表。这题的空间复杂度要求 O(1)所以不能用递归版本递归栈会占 O(log n) 空间。力扣官方解法里提到自底向上的归并排序从长度为 1 的子链表开始逐层合并完全避免递归。但说实话面试的时候递归版本通常就能过关自底向上写法比较复杂容易出错。如果面试官明确要求 O(1) 空间你再上自底向上版本平时练习还是先把递归版本写熟练更重要。2.3 逆序对统计归并排序的高阶用法力扣剑指 Offer 51 题数组中的逆序对以及 LeetCode 第 493 题翻转对都是在归并排序框架里做统计的经典题目。暴力法 O(n²) 必然超时归并排序可以把复杂度降到 O(n log n)。以逆序对为例核心逻辑是在 merge 阶段左右两个子数组都已经有序当nums[i] nums[j]时说明nums[i]到nums[mid]这一整段都大于nums[j]这些元素与nums[j]都构成逆序对所以一次性累加mid - i 1个。def reversePairs(nums): def merge_sort(l, r): if l r: return 0 mid (l r) // 2 count merge_sort(l, mid) merge_sort(mid 1, r) i, j l, mid 1 tmp [] while i mid and j r: if nums[i] nums[j]: tmp.append(nums[i]) i 1 else: tmp.append(nums[j]) count mid - i 1 j 1 while i mid: tmp.append(nums[i]) i 1 while j r: tmp.append(nums[j]) j 1 nums[l:r1] tmp return count return merge_sort(0, len(nums) - 1)这段代码的关键就在count mid - i 1这一行。为什么是mid - i 1而不是别的因为nums[i]都大于nums[j]了而左侧数组是递增的所以从i到mid的所有数都大于nums[j]一共mid - i 1个。这就是逆序对统计的精华所在一次比较累加一片而不是一个一个数。翻转对问题稍微变了一点条件从nums[i] nums[j]变成nums[i] 2 * nums[j]。这导致不能像逆序对那样在合并时直接比较——因为左侧数组虽然有序但不满足大于 2 倍的条件不具备传递性。你需要单独用一个指针去扫描nums[i] 2 * nums[j]的配对然后再走正常的两路归并合并。这也是归并排序框架灵活性的体现你可以在 merge 之前插入任意区间统计逻辑框架不会受影响。3. 更复杂的场景区间和问题中的归并思想3.1 前缀和 归并排序解决区间和计数力扣第 327 题区间和的个数是一道非常隐蔽的归并排序题。题目要求给定一个整数数组nums和两个整数lower、upper返回落在[lower, upper]区间内的子数组和的个数。常规思路是用前缀和配合有序数据结构如平衡树、树状数组来做这些实现起来都不轻松。但实际上这题也可以用归并排序来解决而且思路很顺畅。先看核心转化子数组nums[i:j]的和等于prefix[j] - prefix[i]前缀和之差。我们要找的就是满足lower prefix[j] - prefix[i] upper的二元组(i, j)数量。把前缀和数组拿到手之后这题就变成了统计前缀和数组中有多少对(i, j)满足i j且prefix[j] - prefix[i]落在指定区间内。这和逆序对问题是不是很像都是统计一对元素满足某种条件。逆序对要求prefix[i] prefix[j]这里要求lower prefix[j] - prefix[i] upper。本质上都属于二维偏序问题而归并排序天生擅长处理这类问题——因为分治合并的过程中左右子数组的下标天然满足i j你只需要在合并时快速统计右侧元素相对左侧元素满足条件即可。3.2 归并阶段如何统计区间和的数量关键在于 merge 阶段左右两个子数组的前缀和都已经有序。对于右侧的每个元素prefix[j]我们要找左侧有多少个prefix[i]满足lower prefix[j] - prefix[i] upper等价于prefix[j] - upper prefix[i] prefix[j] - lower。由于左侧子数组有序可以用两个指针 l 和 r 分别维护满足条件的下界和上界位置。对于每个prefix[j]通过移动指针找出符合条件的prefix[i]区间它们全部满足条件。注意这里不能用mid - i 1的方式直接算个数而是要把l和r的位置差算出来r - l就是满足条件的个数。def countRangeSum(nums, lower, upper): prefix [0] for x in nums: prefix.append(prefix[-1] x) def merge_sort(l, r): if l r: return 0 mid (l r) // 2 count merge_sort(l, mid) merge_sort(mid 1, r) i j l for k in range(mid 1, r 1): while i mid and prefix[k] - prefix[i] upper: i 1 while j mid and prefix[k] - prefix[j] lower: j 1 count j - i a sorted(prefix[l:r1]) prefix[l:r1] a return count return merge_sort(0, len(prefix) - 1)这个写法里对左右部分的排序用了一种取巧的方式直接用sorted对区间排序。如果严格考究的话应该单独写一个合并排序的过程但通过对比可以看出核心思想是一样的。面试时建议把这个优化后的版本写出来突出你理解了边合并边统计的过程这样比直接调sorted更有说服力。这类题最大的难点不是代码本身而是把问题转化成前缀和有序数组上二维偏序这一步。一旦跨过这一步后面的归并写法就是一个模板。我强烈建议用这三道题逆序对、翻转对、区间和做一次归并排序的专题训练练完你会对分治框架有完全不同的感觉。4. 归并排序刷题的正确打开方式4.1 三步定位法判断题目是否能用归并排序我刷了上百道题之后总结出一个判断标准分享给你看到题目描述里出现统计有多少对、满足某种大小关系的组合数量、子区间这类关键词而且暴力法明显是 O(n²)就可以往归并排序的方向想。具体来说分三步走找元素对题目是否涉及两个元素的某种关系比如nums[i] nums[j]、nums[i] 2 * nums[j]、prefix[j] - prefix[i]的范围确认下标关系这两个元素是否有明确的先后顺序要求即i j尝试分治如果左右两半子数组有序是否能快速完成跨区间的统计。如果三步都满足归并排序大概率能给出一个干净利落的 O(n log n) 解法。尤其是第三步这是归并排序相对线段树、树状数组的核心优势——不需要额外的数据结构只需要在递归回溯时插入一段统计代码。4.2 归并排序模板的写法心得网上关于归并排序的模板很多但我觉得最适合力扣场景的是一个整体式写法把排序结果直接覆盖回原数组用辅助数组避免频繁创建列表。def merge_sort(nums, left, right, tmp): if left right: return mid (left right) // 2 merge_sort(nums, left, mid, tmp) merge_sort(nums, mid 1, right, tmp) i, j, k left, mid 1, left while i mid and j right: if nums[i] nums[j]: tmp[k] nums[i] i 1 else: tmp[k] nums[j] j 1 k 1 while i mid: tmp[k] nums[i] i 1 k 1 while j right: tmp[k] nums[j] j 1 k 1 for p in range(left, right 1): nums[p] tmp[p]辅助数组 tmp 是复用的只在最外层创建一次避免每次递归都申请新列表。这个细节在数据量大时能明显减少耗时。另外nums[i] nums[j]这个写法保证了稳定性相等元素优先取左边的排序后它们的相对顺序不变。我在实际使用中发现把for p in range(left, right 1)这段覆盖逻辑放在合并完成后立刻执行而不是等回溯到上层再统一处理可以让后面的区间统计代码保持简洁。因为每次合并完成后整个区间的数据就已经是有序状态了上层递归的统计逻辑可以信赖这个前提。4.3 力扣刷题顺序建议如果你正在准备面试或者系统学习归并排序我建议按这个顺序刷题由易到难逐步建立手感题目难度核心考点合并两个有序数组简单双指针合并基础排序数组中等经典归并排序实现排序链表中等链表拆分 合并数组中的逆序对困难归并框架内统计翻转对困难归并前额外统计逻辑区间和的个数困难前缀和 二维偏序前两题用来巩固模板第三题锻炼链表操作和快慢指针后三题才是归并排序的真正试炼场。你会发现一旦练完后面三道题再回头看前两题已经完全没有难度了。这就是以难带易的进阶路径。5. 归并排序常见错误与调试实录5.1 边界条件写错导致死循环或漏数最常见的错误就是边界条件混乱。我见过太多人写成这样的代码while i mid and j r:或者mid (left right) // 2 merge_sort(nums, left, mid - 1) merge_sort(nums, mid, right)这些写法在某些输入下会出问题轻则统计漏掉一些组合重则栈溢出死循环。归并排序的区间写法其实很讲究我建议统一用闭区间[left, right]每次拆成[left, mid]和[mid 1, right]两段这样递归终止条件是left right直白且不容易错。如果你是左闭右开区间党那就要统一用[left, right)拆成[left, mid)和[mid, right)。两个区间在mid处无缝衔接递归终止条件写成right - left 1。哪种写法都可以但千万不要混用混用是 off-by-one 错误的最大根源。5.2 统计逻辑放错位置归并排序框架里可以插入统计逻辑但统计代码放在哪个循环里、放在哪一层递归里是有讲究的。逆序对和翻转对的统计发生在真正归并的过程中它们和元素的移动是同步的。但区间和问题是先做统计再做排序统计时必须依赖左右两侧已经有序。如果你把区间和的统计逻辑放在归并之后发现排序把原数组的顺序打乱了统计结果就会出错。我的习惯是在归并排序函数中先做所有需要有序前提的统计然后再执行归并排序本身。这样逻辑清晰也不容易漏。另外逆序对统计里count是累加到递归函数返回值的但如果使用全局变量要注意在每次测试用例后重置。力扣的测试跑在同一进程里全局变量如果不重置会带脏数据影响后续测试很多人在第 493 题翻转对上栽过这个跟头。5.3 复杂度被误判链表归并的递归坑链表版本的归并排序时间复杂度虽然是 O(n log n)但如果使用递归空间复杂度其实是 O(log n)——这来自递归栈的调用深度。真正严格的 O(1) 空间版本需要自底向上的迭代写法力扣官方题解里用了一个subLength变量控制每次合并的子链表长度。我建议你在面试时主动说明这一点面试官往往会为这个细节加分。如果你时间充裕建议把自底向上的版本也写一遍这个过程中你会对链表的操作有更深的理解。5.4 关于堆溢出与运行时间的实测心得Python 对大规模数据跑归并排序性能瓶颈通常在递归深度和数组切片。nums[l:r1] tmp这类切片操作虽然方便但会在底层新建列表数据量大时内存开销明显。我在实测 10 万级数据时切片式写法比辅助数组覆盖方式慢大约 20%~30%。刷题虽然不卡那么严但养成省内存的好习惯没有坏处。另外一个坑是 Python 默认递归深度限制是 1000 层。归并排序递归深度是 log n 级别10 万数据只需 17 层递归所以一般不用改递归深度。但如果你的归并排序实现里区间拆分写错了导致递归深度变成 n 级别就会直接触发RecursionError。看到这个报错先检查边界条件别急着调大递归限制。6. 归并排序题目的扩展思考6.1 从力扣题到面试题怎么回答讲讲归并排序面试官问归并排序时最常期待的表述是先讲整体思路——分治分解成子问题递归处理然后合并有序子序列再讲时间复杂度推导——每次合并 O(n)递归深度 O(log n)总复杂度 O(n log n)接着讲空间复杂度——辅助数组 O(n)最后提稳定性——归并排序是稳定排序。如果你能在某个环节自然地引入那几道力扣题中的变形比如逆序对问题就是在归并过程中顺带统计的面试官通常会对你的理解留下好印象。说明你不只是背了模板而是真的理解了分治框架的扩展能力。6.2 归并与快排的适用场景对比很多人会把归并排序和快速排序放在一起比较。简单来说快排的常数因子更小、空间 O(log n)、最坏情况 O(n²)适合通用排序场景归并排序稳定、复杂度恒定 O(n log n)、支持分治统计适合需要排序 统计配合的场景。在力扣刷题时如果排序结果本身不是目的而是解决某个更复杂问题的中间步骤归并排序往往更合适。比如数组中的逆序对你也能用树状数组做但归并排序在思路和编码复杂度上都更友好不需要额外学习数据结构。6.3 一个进阶方向多路归并与外部排序归并排序的思想可以自然扩展到 K 路归并也就是多路归并。力扣第 23 题合并 K 个升序链表就是典型的多路归并用优先队列维护 K 个链表的头节点每次取最小时间复杂度 O(N log K)。严格说它不属于经典归并排序但思想同源。真正的多路归并在大数据领域应用更广当数据量大到无法全部载入内存时先分块排序写入磁盘再用多路归并把多个有序文件合并成一个。这是我读书时做数据库课程设计遇到的场景实践下来对分治 有序合并这个思想的理解会更深。如果你对归并排序已经掌握得不错可以去看看外排序的算法流程会有种原来如此的通透感。7. 一个完整的归并排序题刷题复盘最后做个小复盘。我按照上面提到的路线刷完逆序对、翻转对、区间和这三道题后最大的收获不是记住了三个模板而是真正理解了有序性的价值。为什么归并排序能在 O(n log n) 时间内解决暴力需要 O(n²) 的问题因为它通过分治不断制造局部有序的环境使得每次比较都能以一当十。而今天的四道题从合并两个有序数组到排序链表到逆序对再到区间和本质上都在反复调用归并排序的分治框架。你会发现后面的难题并没有引入全新的算法思想只是在 merge 阶段多加了一些统计逻辑。这让我想起一句老话算法题的本质是组合已有的思想而不是发明新的思想。归并排序这个框架就是这些年最值得复用和深挖的框架之一。如果你刷题时遇到了卡壳不妨回到归并排序最基本的合并过程把两个有序数组合并的代码写到肌肉记忆的程度再去啃那些归并 统计的题目你会清晰很多。我个人在实际操作中的体会是归并排序不是一道题而是一类题。另外想提醒一句练习归并排序时一定不要跳过排序链表这题。很多人觉得链表的归并和一维数组差不多实际上手会发现快慢指针找中点、断链、合并三个步骤环环相扣每一步都有细节。练完链表版你对归并排序框架的驾驭能力会上一个台阶。说到底归并排序在力扣题里的价值从来不只是把无序变成有序这一件事。它通过分治让复杂度从 O(n²) 降到 O(n log n)通过合并让统计可以和排序同步完成通过稳定性保证了相等元素的相对顺序。这三个特性单独拿出来都很普通但组合在一起就成了解决一类问题的利器。刷题的时候多想想这三个特性分别对应什么场景你的算法直觉会越来越准。
