归并排序在力扣里是个很特别的存在。你说它是基础题吧直接让你背模板的题确实不多但你说它是冷门算法吧一到中等偏上的题比如逆序对、排序链表、区间和统计归并排序的思路几乎无处不在。很多同学刷到“排序数组”这类题时觉得归并排序就是两种写法选一种背下来就行等到刷“计算右侧小于当前元素的个数”时才发现自己压根没理解归并排序的合并过程到底在干什么。这篇文章我想把归并排序从力扣入门模板题到高阶变形题的完整链路拆开讲清楚适合刚开始刷排序题的新手也适合那些能把归并排序代码默写出来、但一变型就卡壳的进阶选手。1. 归并排序到底在力扣里考什么1.1 标题背后的核心考点“归并排序力扣题”这个组合看起来很简单但它背后其实覆盖了三层能力。第一层是基本功也就是能用归并排序给一个数组排序这是排序数组这道题的直接要求。第二层是分治思想归并排序是典型的分治算法把一个大规模问题拆成两个小规模问题分别解决后再合并结果这种“拆解-递归-合并”的思路在力扣里被反复使用。第三层才是真正拉开差距的地方归并排序的合并过程天然是一个“顺序比较两个有序序列”的过程这个过程可以顺带统计逆序对、计算右侧更小元素数量、甚至累加区间和很多困难题实际上就是在合并那一步偷偷加了一个计数器。所以你在力扣刷归并排序不能只满足于“把数组排好序”。你要理解每次合并时左半部分元素和右半部分元素的相对位置关系理解当一个右半部分元素先被放回数组时它“越过”了多少个左半部分元素理解这种跨越次数对应什么统计意义。把这些想通了归并排序就不再是一道模板题而是你解决一系列计算类题目的底层工具。1.2 适合谁来读这篇如果你是刚开始刷力扣建议先掌握递归版归并排序的写法然后按照我的顺序做三道题排序数组、数组中的逆序对、排序链表。这三道题能把归并排序的基础模板、统计变型、链表变型全部覆盖。如果你已经刷过这些题但感觉很吃力那重点看我对于合并过程的分析尤其是临时数组的索引处理和逆序对计数的位置关系。如果你是想系统突破困难题那么计算右侧小于当前元素的个数和区间和的个数这两道题值得反复琢磨它们展示了归并排序如何从“排序工具”升华为“解题框架”。2. 归并排序的原理与代码落地2.1 分治三步走拆、排、合归并排序的核心思想非常朴素如果给你两个已经排好序的数组合并成一个有序数组是很容易的双指针依次比较就行。但原始数组是乱序的那怎么办分治的思路是先把数组从中间一分为二左半边递归排序右半边递归排序最后把两个有序数组合并。这个流程可以拆成三条清晰的动作路径。第一确定中点索引通常用left (right - left) / 2而不是(left right) / 2主要目的是防止两个大整数相加时溢出虽然力扣的测试数据一般不会触发这个问题但这是个代码习惯问题。第二递归调用自身分别处理左区间和右区间直到区间里只剩一个元素一个元素天然有序这就是递归的终止条件。第三合并两个有序区间这一步需要额外开辟一个临时数组把左右两个区间的元素按大小顺序填入临时数组最后再拷贝回原数组的对应位置。“合并”这个动作是归并排序的灵魂。每次合并时左区间内部已经有序右区间内部也已经有序但左区间的所有元素和右区间的所有元素之间还没有统一排序。双指针从左区间起点和右区间起点开始往后移动谁小谁就先进临时数组。这个过程听起来简单但如果你自己动手模拟一遍就会发现它本质上是把所有元素重新排列了一遍而且因为左右区间分别有序每个元素的移动路径都遵循“要么在自己区间内后移要么越过对方区间的若干元素”。2.2 递归版代码最常见的写法先给出一版最经典的递归实现用来解决力扣912. 排序数组是完全足够的。class Solution: def sortArray(self, nums: List[int]) - List[int]: n len(nums) # 临时数组只开一次避免递归过程中反复创建 tmp [0] * n def merge_sort(left: int, right: int): if left right: return mid left (right - left) // 2 merge_sort(left, mid) merge_sort(mid 1, right) # 合并两个有序区间 [left, mid] 和 [mid1, right] i, j left, mid 1 k 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 idx in range(left, right 1): nums[idx] tmp[idx] merge_sort(0, n - 1) return nums这里有两个容易忽略的细节。第一个是临时数组的分配位置我把它放在sortArray函数里统一创建然后通过闭包方式让内部函数共享。如果每次递归都新建一个临时数组那总空间复杂度会从O(n)变成O(n log n)力扣对空间复杂度要求不严的时候能过但在排序链表那道题里如果你延续这个习惯会遇到链表的合并需要不断新建节点的性能问题。第二个细节是比较时用而不是这保证了相等元素的相对顺序不变也就是排序稳定性。在力扣里稳定性通常不直接作为考点但在逆序对统计类题目里相等的元素不应该被计入逆序对所以这里的等号处理很关键。2.3 迭代版归并与复杂度分析递归版的归并排序虽然好懂但有些同学在面试中会被追问“不用递归怎么写”。迭代版的思路是把整个数组看成一个个长度为1的有序片段然后两两合并成长度为2的有序片段再合并成长度为4的片段直到整个数组有序。class Solution: def sortArray(self, nums: List[int]) - List[int]: n len(nums) tmp [0] * n width 1 while width n: for left in range(0, n, 2 * width): mid min(left width - 1, n - 1) right min(left 2 * width - 1, n - 1) if mid right: continue # 合并 [left, mid] 和 [mid1, right] 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 idx in range(left, right 1): nums[idx] tmp[idx] width * 2 return nums迭代版的边界条件是这道题最容易出错的地方。width表示当前每个有序片段的长度初始为1每轮翻倍。left从0开始每次跨过一个2 * width因为两个片段合并后长度变成2 * width。如果最后一个片段长度不够mid和right都通过min限制在数组末尾。有一个点很多人第一次写会漏掉如果mid right说明只剩一个片段了不需要合并直接跳过。时间复杂度和空间复杂度在递归版和迭代版里完全一样。时间复杂度是O(n log n)每一层要处理n个元素一共log n层。空间复杂度是O(n)主要是临时数组的开销递归栈的深度是O(log n)但O(n)级别的主导是临时数组。这个复杂度特性在力扣题目里经常成为解题依据当题目要求O(n log n)的时间复杂度和O(n)的空间复杂度时归并排序往往就是默认答案。3. 力扣经典题的三种考法3.1 纯考模板912. 排序数组这道题是归并排序在力扣里的“主战场”之一。题目要求很简单给一个整数数组升序排列。很多人第一反应是调用内置排序但刷题的意义在于掌握底层算法。用归并排序做这道题代码就是我在前面给出的递归版。不过这道题有一个需要留心的点测试数据里包含大量元素和极端分布比如[5,1,1,2,0,0]这种大量相等元素的情况会考验排序的稳定性。我建议把递归版代码默写到肌肉记忆级别。怎么检验自己有没有真正掌握不看任何资料在纸上手动模拟一个长度为8的数组的完整归并过程写出每一层递归的调用顺序和每一次合并后的数组状态。如果这一步能顺利做出来说明你理解了递归的展开过程如果只能背代码而不能手动模拟那你做后面的变型题一定会卡住。3.2 经典变形数组中的逆序对这道题在很多平台都有力扣上对应的是剑指 Offer 51. 数组中的逆序对。题目定义如果i j且nums[i] nums[j]那么(i, j)是一个逆序对统计数组中所有逆序对的数量。暴力解法是双重循环时间复杂度O(n²)数据规模稍大就超时。归并排序可以在O(n log n)时间内完成统计。核心思路藏在合并过程里。当两个有序区间[left, mid]和[mid1, right]在合并时如果左区间当前元素nums[i]大于右区间当前元素nums[j]那么说明左区间从i到mid的所有元素都大于nums[j]因为左区间是升序的。所以当nums[j]被放进临时数组时产生了mid - i 1个逆序对。代码实现如下class Solution: def reversePairs(self, nums: List[int]) - int: n len(nums) tmp [0] * n self.count 0 def merge_sort(left: int, right: int): if left right: return mid left (right - left) // 2 merge_sort(left, mid) merge_sort(mid 1, right) 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 # 关键统计逻辑 self.count mid - i 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 idx in range(left, right 1): nums[idx] tmp[idx] merge_sort(0, n - 1) return self.count这里最需要注意的就是等号的比较。当nums[i] nums[j]时不计数因为nums[i]和nums[j]相等时不应该算作逆序对。每次移动右区间指针j时左区间剩余元素数量就是mid - i 1这个数量就是当前nums[j]与左区间剩余元素构成的逆序对个数。我用一个具体例子说明。假设合并时左区间是[2, 5, 7]右区间是[1, 3, 6]。开始时i指向2j指向1因为2 1所以右区间的1需要合并进来此时左区间三个元素都比1大产生3个逆序对。继续移动j到3此时nums[i]2不大于3左区间指针后移nums[i]5大于3产生2个逆序对。这个过程中你实际上是在每个右区间元素进入有序序列时一次性统计它与左区间所有遗留元素的逆序关系归并排序之所以高效就是因为它把这种统计批量完成了。3.3 链表版本148. 排序链表这道题要求在O(n log n)时间复杂度和O(1)空间复杂度下对链表排序。看到这个复杂度要求首先想到的算法就是归并排序。数组版归并排序需要O(n)辅助空间但链表版可以通过修改节点引用来实现原地归并不需要额外数组。链表版的两个关键点。第一个是找链表中点这要用快慢指针快指针每次走两步慢指针每次走一步快指针到末尾时慢指针正好在中点。这里注意偶数节点链表的中点选取会影响后续递归切分的正确性建议手动画一个4个节点的链表模拟一遍。第二个是两个有序链表的合并可以用一个虚拟头节点来简化操作每次比较两个链表头节点的大小把较小的节点接到新链表尾部。class Solution: def sortList(self, head: Optional[ListNode]) - Optional[ListNode]: 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 # 断开链表 left self.sortList(head) right self.sortList(mid) # 合并两个有序链表 dummy ListNode(0) cur dummy while left and right: if left.val right.val: cur.next left left left.next else: cur.next right right right.next cur cur.next cur.next left if left else right return dummy.next链表版和数组版共用一个分治框架但实现上的差异很大。数组版通过索引切分区间链表版需要断开节点来切分数组版合并时要拷贝到临时数组再拷回来链表版则只需要调整引用。很多同学做这道题时会犯一个经典错误使用快慢指针找中点时fast初始化为head而不是head.next这会导致链表长度为2时出现死循环因为slow无法正确到达中点递归切分无法推进。我个人的习惯是slow headfast head.next这样当链表长度为2时slow正好停在第一个节点mid是第二个节点能正确切成两个长度为1的链表。3.4 扩展题型315. 计算右侧小于当前元素的个数这道题是逆序对问题的一次升级。题目要求对每个元素统计它右侧有多少个更小的元素。暴力解法同样是O(n²)而利用归并排序可以在合并过程中统计每个元素“从右侧越过来”的次数。思路是这样的归并排序过程中当右区间元素nums[j]被放入临时数组时意味着它比左区间当前元素小。但是这道题要求的是每个位置独立的结果不能只统计总数。所以需要维护一个索引数组让元素带着原始下标一起移动在合并过程中每当一个右区间元素被合并进来它就是在“告诉”左区间当前元素以及左区间剩余的所有元素你们右侧又多了一个比我小的数。实现时用一个index数组记录每个元素在原数组中的位置。排序时比较的是nums的值但移动的其实是index数组里的索引。合并过程中如果右区间元素先被放入临时索引数组说明左区间当前元素以及后续元素右侧都比它多了一个更小的元素于是把这些左区间元素的答案全部加1。这里如果每个元素都逐个加1会退化成O(n²)更好的做法是维护一个数组记录偏移量在最终遍历时一次性计算。不过就力扣这道题的数据范围来说常规逐个统计在归并框架下也能通过。核心思想是理解了实现细节可以根据自己的代码风格调整。4. 归并排序的进阶应用与思路迁移4.1 区间统计类问题的套路327. 区间和的个数这道题乍一看和归并排序没什么关系它要求统计数组中有多少子数组的和落在[lower, upper]范围内。常规前缀和思路是枚举所有子数组需要O(n²)超时。但如果你把前缀和数组当成归并排序的输入问题就转化成在合并两个有序前缀和区间时统计左区间每个元素sum[i]在右区间中有多少个sum[j]满足sum[j] - sum[i]落在给定区间内。这一步的关键在于前缀和数组经过归并排序后是有序的那么对于固定的左区间元素右区间中满足条件的元素一定是一段连续区间可以用双指针确定边界。这就把“统计数量”变成了“在有序数组中找连续区间”每次合并能在线性时间内完成统计整体复杂度依然是O(n log n)。这种变形题的启示是归并排序不只是排序它还是一个“在分治过程中对两个有序序列进行局部统计”的框架。你不需要对整个数组进行全局扫描因为分治天然把问题拆成了两半每一半内部有序你只需要考虑跨左右两半的统计关系。这一点和逆序对、右侧更小元素都是同一个套路。4.2 归并排序和树状数组怎么选在我刷力扣的过程中经常遇到逆序对类题目下面有人讨论树状数组。确实比如计算右侧小于当前元素的个数树状数组也能做而且思路上是“维护值域上的桶从右往左遍历查询比当前值小的数量”。两种做法的取舍主要看数据范围和数据特性。树状数组的思路是把每个值映射到值域索引上每次查询和更新都是O(log n)总复杂度也是O(n log n)但它需要离散化而且理解门槛比归并排序高。归并排序的优点是模板代码相对固定你只需要在合并代码里加几行统计逻辑不需要离散化而且天然处理了重复元素的顺序关系。缺点是它修改了原数组的顺序如果你需要保留原始位置信息就要像315题那样额外维护索引数组。我个人刷题时的选择标准是如果是面试沟通我优先讲归并排序因为分治思想更容易一步步引导面试官也更容易理解你的推导过程。如果数据范围特别大大到归并排序的空间复杂度吃紧那就考虑树状数组。但绝大多数力扣题归并排序的处理方式都够用而且更直观。4.3 从归并排序到外部排序这个扩展已经超出力扣范围了但对理解归并排序的“合并有序序列”思想非常有帮助。真实业务中如果数据量大到内存装不下比如要对几百GB的日志文件排序该怎么办思路就是把大文件切分成多个小块每块分别读入内存排序后写回磁盘形成多个有序临时文件然后用一个多路归并的过程把所有临时文件合并成一个有序大文件。这个过程本质上就是归并排序中“合并两个有序数组”的扩展版只是合并对象换成了多个文件。理解这一点有什么用刷题时你可能不会直接遇到外部排序但遇到合并K个有序链表、合并K个有序数组这类题目时你会发现它们的核心诉求和外部排序的多路归并是一致的每次从多个有序序列中取最小值放入结果序列中。掌握了归并排序的合并思想这些题你至少会有一个清晰的起点。5. 实战踩坑与调试心得5.1 递归爆栈问题力扣的排序数组题数组长度通常是10^5级别归并排序的递归深度是log n大约17层根本不会爆栈。但如果你的递归终止条件写错了比如把if left right写成了if left right在区间为空时会无限递归最终栈溢出。排查这种问题最快的办法是打印递归参数看看left和right是否出现了left right的情况。另外提醒一下Python的递归深度默认是1000如果你写算法时用了递归并且数组规模特别大比如在本地测试10^6级别数据log n深度虽然远小于1000但你还是要注意递归函数每层持有的局部变量占用尤其是临时数组的切片操作。我见过有人图省事在递归里写nums[left:mid1]这种切片每层递归都会复制一次数组空间复杂度直接爆炸。5.2 合并过程索引错乱归并排序出错率最高的位置就是合并那一段的索引。最常见的错误是临时数组的写入位置和拷贝回原数组的位置对不上。我见过很多次这样的场景k初始化为0把结果写在临时数组开头但拷贝回原数组时却从left开始导致只拷贝了right - left 1个元素但来源起始位置不对。我的建议是把k初始化为left这样临时数组的写入位置和原数组的区间起点一致后续拷贝用for idx in range(left, right 1)就能一一对应不容易错。另一个容易错的地方是第二个while循环。前面双指针合并结束后左区间或右区间可能还有剩余元素两个while分别处理剩余元素。如果漏掉元素会丢失。这个和归并排序的执行过程有关双指针循环跳出的条件是两个指针之一越界剩下那一区间的元素一定整体大于已放入临时数组的所有元素所以直接顺序拷贝即可。5.3 临时数组共享问题我在 2.2 节里强调过临时数组只创建一次。这里补充一个反面例子。如果每次递归都创建临时数组在递归返回后临时数组就会被释放然后在合并阶段又重新创建这个过程中不断分配和释放内存虽然功能上不会出错但性能会明显下降。在力扣上表现就是耗时偏高在面试中写这种代码也会被追问空间复杂度细节。还有一类共享问题是闭包变量覆盖。如果你在循环里重复调用归并排序函数或者用类的成员变量存储临时数组要确保每次调用前临时数组被正确重置。比如逆序对题如果同一个测试用例里多次调用函数count成员变量没有被清零会累加出错误答案。我的习惯是在入口函数里显式重置统计变量不要依赖默认值。5.4 力扣判题中的边界用例排序类题目最常见的边界用例包括空数组、单元素数组、全部相等元素、降序排列的极端输入。空数组和单元素数组在归并排序里直接返回不会出错但你要确认自己的代码在这个场景下没有访问nums[0]这类操作。全部相等元素是检验稳定性的好用例如果你用而不是进行比较排序结果看起来依然正确但在逆序对统计题里相等元素会被错误计为逆序对。极端降序输入则是逆序对数量最大的情况一个[5,4,3,2,1]的数组共有10个逆序对你可以用这个最简单的例子验证自己的统计逻辑是否正确。6. 把归并排序练成肌肉记忆的个人经验我个人实践下来归并排序确实是力扣里“投入产出比”最高的几个算法之一因为它的核心过程足够固定从模板到逆序对到链表版可以在两三天内全部吃透而且一旦吃透后续遇到统计类困难题时你会发现解法里总有归并排序的影子。给你几个我亲测有效的练习步骤第一步不看代码手动模拟一遍长度为8的数组的完整归并过程写在纸上这一步决定你是否真的理解了递归展开。第二步按顺序刷排序数组、数组中的逆序对、排序链表每道题都自己重新默写代码不要复制粘贴。第三步把三个版本的代码放在一起对比找出它们的共同骨架和差异点这个过程能帮你建立“分治合并”的思维模板。第四步挑战计算右侧小于当前元素的个数如果你能独立做出来归并排序这块你基本过关了。最后再分享一个小细节刷题时不要只关注答案是否正确每次提交后看下耗时和内存的分布曲线归并排序的耗时通常应该在排序类题目的中上水平如果你明显偏慢检查一下是不是在递归里做了数组切片或者重复创建临时数组。这些细节才是刷题经验里最值钱的部分。 
长河君 · 2026/10/20 5:55:24 · 阅读 1.2k 归并排序力扣全攻略：模板、逆序对与链表变形
归并排序在力扣里是个很特别的存在。你说它是基础题吧直接让你背模板的题确实不多但你说它是冷门算法吧一到中等偏上的题比如逆序对、排序链表、区间和统计归并排序的思路几乎无处不在。很多同学刷到“排序数组”这类题时觉得归并排序就是两种写法选一种背下来就行等到刷“计算右侧小于当前元素的个数”时才发现自己压根没理解归并排序的合并过程到底在干什么。这篇文章我想把归并排序从力扣入门模板题到高阶变形题的完整链路拆开讲清楚适合刚开始刷排序题的新手也适合那些能把归并排序代码默写出来、但一变型就卡壳的进阶选手。1. 归并排序到底在力扣里考什么1.1 标题背后的核心考点“归并排序力扣题”这个组合看起来很简单但它背后其实覆盖了三层能力。第一层是基本功也就是能用归并排序给一个数组排序这是排序数组这道题的直接要求。第二层是分治思想归并排序是典型的分治算法把一个大规模问题拆成两个小规模问题分别解决后再合并结果这种“拆解-递归-合并”的思路在力扣里被反复使用。第三层才是真正拉开差距的地方归并排序的合并过程天然是一个“顺序比较两个有序序列”的过程这个过程可以顺带统计逆序对、计算右侧更小元素数量、甚至累加区间和很多困难题实际上就是在合并那一步偷偷加了一个计数器。所以你在力扣刷归并排序不能只满足于“把数组排好序”。你要理解每次合并时左半部分元素和右半部分元素的相对位置关系理解当一个右半部分元素先被放回数组时它“越过”了多少个左半部分元素理解这种跨越次数对应什么统计意义。把这些想通了归并排序就不再是一道模板题而是你解决一系列计算类题目的底层工具。1.2 适合谁来读这篇如果你是刚开始刷力扣建议先掌握递归版归并排序的写法然后按照我的顺序做三道题排序数组、数组中的逆序对、排序链表。这三道题能把归并排序的基础模板、统计变型、链表变型全部覆盖。如果你已经刷过这些题但感觉很吃力那重点看我对于合并过程的分析尤其是临时数组的索引处理和逆序对计数的位置关系。如果你是想系统突破困难题那么计算右侧小于当前元素的个数和区间和的个数这两道题值得反复琢磨它们展示了归并排序如何从“排序工具”升华为“解题框架”。2. 归并排序的原理与代码落地2.1 分治三步走拆、排、合归并排序的核心思想非常朴素如果给你两个已经排好序的数组合并成一个有序数组是很容易的双指针依次比较就行。但原始数组是乱序的那怎么办分治的思路是先把数组从中间一分为二左半边递归排序右半边递归排序最后把两个有序数组合并。这个流程可以拆成三条清晰的动作路径。第一确定中点索引通常用left (right - left) / 2而不是(left right) / 2主要目的是防止两个大整数相加时溢出虽然力扣的测试数据一般不会触发这个问题但这是个代码习惯问题。第二递归调用自身分别处理左区间和右区间直到区间里只剩一个元素一个元素天然有序这就是递归的终止条件。第三合并两个有序区间这一步需要额外开辟一个临时数组把左右两个区间的元素按大小顺序填入临时数组最后再拷贝回原数组的对应位置。“合并”这个动作是归并排序的灵魂。每次合并时左区间内部已经有序右区间内部也已经有序但左区间的所有元素和右区间的所有元素之间还没有统一排序。双指针从左区间起点和右区间起点开始往后移动谁小谁就先进临时数组。这个过程听起来简单但如果你自己动手模拟一遍就会发现它本质上是把所有元素重新排列了一遍而且因为左右区间分别有序每个元素的移动路径都遵循“要么在自己区间内后移要么越过对方区间的若干元素”。2.2 递归版代码最常见的写法先给出一版最经典的递归实现用来解决力扣912. 排序数组是完全足够的。class Solution: def sortArray(self, nums: List[int]) - List[int]: n len(nums) # 临时数组只开一次避免递归过程中反复创建 tmp [0] * n def merge_sort(left: int, right: int): if left right: return mid left (right - left) // 2 merge_sort(left, mid) merge_sort(mid 1, right) # 合并两个有序区间 [left, mid] 和 [mid1, right] i, j left, mid 1 k 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 idx in range(left, right 1): nums[idx] tmp[idx] merge_sort(0, n - 1) return nums这里有两个容易忽略的细节。第一个是临时数组的分配位置我把它放在sortArray函数里统一创建然后通过闭包方式让内部函数共享。如果每次递归都新建一个临时数组那总空间复杂度会从O(n)变成O(n log n)力扣对空间复杂度要求不严的时候能过但在排序链表那道题里如果你延续这个习惯会遇到链表的合并需要不断新建节点的性能问题。第二个细节是比较时用而不是这保证了相等元素的相对顺序不变也就是排序稳定性。在力扣里稳定性通常不直接作为考点但在逆序对统计类题目里相等的元素不应该被计入逆序对所以这里的等号处理很关键。2.3 迭代版归并与复杂度分析递归版的归并排序虽然好懂但有些同学在面试中会被追问“不用递归怎么写”。迭代版的思路是把整个数组看成一个个长度为1的有序片段然后两两合并成长度为2的有序片段再合并成长度为4的片段直到整个数组有序。class Solution: def sortArray(self, nums: List[int]) - List[int]: n len(nums) tmp [0] * n width 1 while width n: for left in range(0, n, 2 * width): mid min(left width - 1, n - 1) right min(left 2 * width - 1, n - 1) if mid right: continue # 合并 [left, mid] 和 [mid1, right] 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 idx in range(left, right 1): nums[idx] tmp[idx] width * 2 return nums迭代版的边界条件是这道题最容易出错的地方。width表示当前每个有序片段的长度初始为1每轮翻倍。left从0开始每次跨过一个2 * width因为两个片段合并后长度变成2 * width。如果最后一个片段长度不够mid和right都通过min限制在数组末尾。有一个点很多人第一次写会漏掉如果mid right说明只剩一个片段了不需要合并直接跳过。时间复杂度和空间复杂度在递归版和迭代版里完全一样。时间复杂度是O(n log n)每一层要处理n个元素一共log n层。空间复杂度是O(n)主要是临时数组的开销递归栈的深度是O(log n)但O(n)级别的主导是临时数组。这个复杂度特性在力扣题目里经常成为解题依据当题目要求O(n log n)的时间复杂度和O(n)的空间复杂度时归并排序往往就是默认答案。3. 力扣经典题的三种考法3.1 纯考模板912. 排序数组这道题是归并排序在力扣里的“主战场”之一。题目要求很简单给一个整数数组升序排列。很多人第一反应是调用内置排序但刷题的意义在于掌握底层算法。用归并排序做这道题代码就是我在前面给出的递归版。不过这道题有一个需要留心的点测试数据里包含大量元素和极端分布比如[5,1,1,2,0,0]这种大量相等元素的情况会考验排序的稳定性。我建议把递归版代码默写到肌肉记忆级别。怎么检验自己有没有真正掌握不看任何资料在纸上手动模拟一个长度为8的数组的完整归并过程写出每一层递归的调用顺序和每一次合并后的数组状态。如果这一步能顺利做出来说明你理解了递归的展开过程如果只能背代码而不能手动模拟那你做后面的变型题一定会卡住。3.2 经典变形数组中的逆序对这道题在很多平台都有力扣上对应的是剑指 Offer 51. 数组中的逆序对。题目定义如果i j且nums[i] nums[j]那么(i, j)是一个逆序对统计数组中所有逆序对的数量。暴力解法是双重循环时间复杂度O(n²)数据规模稍大就超时。归并排序可以在O(n log n)时间内完成统计。核心思路藏在合并过程里。当两个有序区间[left, mid]和[mid1, right]在合并时如果左区间当前元素nums[i]大于右区间当前元素nums[j]那么说明左区间从i到mid的所有元素都大于nums[j]因为左区间是升序的。所以当nums[j]被放进临时数组时产生了mid - i 1个逆序对。代码实现如下class Solution: def reversePairs(self, nums: List[int]) - int: n len(nums) tmp [0] * n self.count 0 def merge_sort(left: int, right: int): if left right: return mid left (right - left) // 2 merge_sort(left, mid) merge_sort(mid 1, right) 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 # 关键统计逻辑 self.count mid - i 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 idx in range(left, right 1): nums[idx] tmp[idx] merge_sort(0, n - 1) return self.count这里最需要注意的就是等号的比较。当nums[i] nums[j]时不计数因为nums[i]和nums[j]相等时不应该算作逆序对。每次移动右区间指针j时左区间剩余元素数量就是mid - i 1这个数量就是当前nums[j]与左区间剩余元素构成的逆序对个数。我用一个具体例子说明。假设合并时左区间是[2, 5, 7]右区间是[1, 3, 6]。开始时i指向2j指向1因为2 1所以右区间的1需要合并进来此时左区间三个元素都比1大产生3个逆序对。继续移动j到3此时nums[i]2不大于3左区间指针后移nums[i]5大于3产生2个逆序对。这个过程中你实际上是在每个右区间元素进入有序序列时一次性统计它与左区间所有遗留元素的逆序关系归并排序之所以高效就是因为它把这种统计批量完成了。3.3 链表版本148. 排序链表这道题要求在O(n log n)时间复杂度和O(1)空间复杂度下对链表排序。看到这个复杂度要求首先想到的算法就是归并排序。数组版归并排序需要O(n)辅助空间但链表版可以通过修改节点引用来实现原地归并不需要额外数组。链表版的两个关键点。第一个是找链表中点这要用快慢指针快指针每次走两步慢指针每次走一步快指针到末尾时慢指针正好在中点。这里注意偶数节点链表的中点选取会影响后续递归切分的正确性建议手动画一个4个节点的链表模拟一遍。第二个是两个有序链表的合并可以用一个虚拟头节点来简化操作每次比较两个链表头节点的大小把较小的节点接到新链表尾部。class Solution: def sortList(self, head: Optional[ListNode]) - Optional[ListNode]: 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 # 断开链表 left self.sortList(head) right self.sortList(mid) # 合并两个有序链表 dummy ListNode(0) cur dummy while left and right: if left.val right.val: cur.next left left left.next else: cur.next right right right.next cur cur.next cur.next left if left else right return dummy.next链表版和数组版共用一个分治框架但实现上的差异很大。数组版通过索引切分区间链表版需要断开节点来切分数组版合并时要拷贝到临时数组再拷回来链表版则只需要调整引用。很多同学做这道题时会犯一个经典错误使用快慢指针找中点时fast初始化为head而不是head.next这会导致链表长度为2时出现死循环因为slow无法正确到达中点递归切分无法推进。我个人的习惯是slow headfast head.next这样当链表长度为2时slow正好停在第一个节点mid是第二个节点能正确切成两个长度为1的链表。3.4 扩展题型315. 计算右侧小于当前元素的个数这道题是逆序对问题的一次升级。题目要求对每个元素统计它右侧有多少个更小的元素。暴力解法同样是O(n²)而利用归并排序可以在合并过程中统计每个元素“从右侧越过来”的次数。思路是这样的归并排序过程中当右区间元素nums[j]被放入临时数组时意味着它比左区间当前元素小。但是这道题要求的是每个位置独立的结果不能只统计总数。所以需要维护一个索引数组让元素带着原始下标一起移动在合并过程中每当一个右区间元素被合并进来它就是在“告诉”左区间当前元素以及左区间剩余的所有元素你们右侧又多了一个比我小的数。实现时用一个index数组记录每个元素在原数组中的位置。排序时比较的是nums的值但移动的其实是index数组里的索引。合并过程中如果右区间元素先被放入临时索引数组说明左区间当前元素以及后续元素右侧都比它多了一个更小的元素于是把这些左区间元素的答案全部加1。这里如果每个元素都逐个加1会退化成O(n²)更好的做法是维护一个数组记录偏移量在最终遍历时一次性计算。不过就力扣这道题的数据范围来说常规逐个统计在归并框架下也能通过。核心思想是理解了实现细节可以根据自己的代码风格调整。4. 归并排序的进阶应用与思路迁移4.1 区间统计类问题的套路327. 区间和的个数这道题乍一看和归并排序没什么关系它要求统计数组中有多少子数组的和落在[lower, upper]范围内。常规前缀和思路是枚举所有子数组需要O(n²)超时。但如果你把前缀和数组当成归并排序的输入问题就转化成在合并两个有序前缀和区间时统计左区间每个元素sum[i]在右区间中有多少个sum[j]满足sum[j] - sum[i]落在给定区间内。这一步的关键在于前缀和数组经过归并排序后是有序的那么对于固定的左区间元素右区间中满足条件的元素一定是一段连续区间可以用双指针确定边界。这就把“统计数量”变成了“在有序数组中找连续区间”每次合并能在线性时间内完成统计整体复杂度依然是O(n log n)。这种变形题的启示是归并排序不只是排序它还是一个“在分治过程中对两个有序序列进行局部统计”的框架。你不需要对整个数组进行全局扫描因为分治天然把问题拆成了两半每一半内部有序你只需要考虑跨左右两半的统计关系。这一点和逆序对、右侧更小元素都是同一个套路。4.2 归并排序和树状数组怎么选在我刷力扣的过程中经常遇到逆序对类题目下面有人讨论树状数组。确实比如计算右侧小于当前元素的个数树状数组也能做而且思路上是“维护值域上的桶从右往左遍历查询比当前值小的数量”。两种做法的取舍主要看数据范围和数据特性。树状数组的思路是把每个值映射到值域索引上每次查询和更新都是O(log n)总复杂度也是O(n log n)但它需要离散化而且理解门槛比归并排序高。归并排序的优点是模板代码相对固定你只需要在合并代码里加几行统计逻辑不需要离散化而且天然处理了重复元素的顺序关系。缺点是它修改了原数组的顺序如果你需要保留原始位置信息就要像315题那样额外维护索引数组。我个人刷题时的选择标准是如果是面试沟通我优先讲归并排序因为分治思想更容易一步步引导面试官也更容易理解你的推导过程。如果数据范围特别大大到归并排序的空间复杂度吃紧那就考虑树状数组。但绝大多数力扣题归并排序的处理方式都够用而且更直观。4.3 从归并排序到外部排序这个扩展已经超出力扣范围了但对理解归并排序的“合并有序序列”思想非常有帮助。真实业务中如果数据量大到内存装不下比如要对几百GB的日志文件排序该怎么办思路就是把大文件切分成多个小块每块分别读入内存排序后写回磁盘形成多个有序临时文件然后用一个多路归并的过程把所有临时文件合并成一个有序大文件。这个过程本质上就是归并排序中“合并两个有序数组”的扩展版只是合并对象换成了多个文件。理解这一点有什么用刷题时你可能不会直接遇到外部排序但遇到合并K个有序链表、合并K个有序数组这类题目时你会发现它们的核心诉求和外部排序的多路归并是一致的每次从多个有序序列中取最小值放入结果序列中。掌握了归并排序的合并思想这些题你至少会有一个清晰的起点。5. 实战踩坑与调试心得5.1 递归爆栈问题力扣的排序数组题数组长度通常是10^5级别归并排序的递归深度是log n大约17层根本不会爆栈。但如果你的递归终止条件写错了比如把if left right写成了if left right在区间为空时会无限递归最终栈溢出。排查这种问题最快的办法是打印递归参数看看left和right是否出现了left right的情况。另外提醒一下Python的递归深度默认是1000如果你写算法时用了递归并且数组规模特别大比如在本地测试10^6级别数据log n深度虽然远小于1000但你还是要注意递归函数每层持有的局部变量占用尤其是临时数组的切片操作。我见过有人图省事在递归里写nums[left:mid1]这种切片每层递归都会复制一次数组空间复杂度直接爆炸。5.2 合并过程索引错乱归并排序出错率最高的位置就是合并那一段的索引。最常见的错误是临时数组的写入位置和拷贝回原数组的位置对不上。我见过很多次这样的场景k初始化为0把结果写在临时数组开头但拷贝回原数组时却从left开始导致只拷贝了right - left 1个元素但来源起始位置不对。我的建议是把k初始化为left这样临时数组的写入位置和原数组的区间起点一致后续拷贝用for idx in range(left, right 1)就能一一对应不容易错。另一个容易错的地方是第二个while循环。前面双指针合并结束后左区间或右区间可能还有剩余元素两个while分别处理剩余元素。如果漏掉元素会丢失。这个和归并排序的执行过程有关双指针循环跳出的条件是两个指针之一越界剩下那一区间的元素一定整体大于已放入临时数组的所有元素所以直接顺序拷贝即可。5.3 临时数组共享问题我在 2.2 节里强调过临时数组只创建一次。这里补充一个反面例子。如果每次递归都创建临时数组在递归返回后临时数组就会被释放然后在合并阶段又重新创建这个过程中不断分配和释放内存虽然功能上不会出错但性能会明显下降。在力扣上表现就是耗时偏高在面试中写这种代码也会被追问空间复杂度细节。还有一类共享问题是闭包变量覆盖。如果你在循环里重复调用归并排序函数或者用类的成员变量存储临时数组要确保每次调用前临时数组被正确重置。比如逆序对题如果同一个测试用例里多次调用函数count成员变量没有被清零会累加出错误答案。我的习惯是在入口函数里显式重置统计变量不要依赖默认值。5.4 力扣判题中的边界用例排序类题目最常见的边界用例包括空数组、单元素数组、全部相等元素、降序排列的极端输入。空数组和单元素数组在归并排序里直接返回不会出错但你要确认自己的代码在这个场景下没有访问nums[0]这类操作。全部相等元素是检验稳定性的好用例如果你用而不是进行比较排序结果看起来依然正确但在逆序对统计题里相等元素会被错误计为逆序对。极端降序输入则是逆序对数量最大的情况一个[5,4,3,2,1]的数组共有10个逆序对你可以用这个最简单的例子验证自己的统计逻辑是否正确。6. 把归并排序练成肌肉记忆的个人经验我个人实践下来归并排序确实是力扣里“投入产出比”最高的几个算法之一因为它的核心过程足够固定从模板到逆序对到链表版可以在两三天内全部吃透而且一旦吃透后续遇到统计类困难题时你会发现解法里总有归并排序的影子。给你几个我亲测有效的练习步骤第一步不看代码手动模拟一遍长度为8的数组的完整归并过程写在纸上这一步决定你是否真的理解了递归展开。第二步按顺序刷排序数组、数组中的逆序对、排序链表每道题都自己重新默写代码不要复制粘贴。第三步把三个版本的代码放在一起对比找出它们的共同骨架和差异点这个过程能帮你建立“分治合并”的思维模板。第四步挑战计算右侧小于当前元素的个数如果你能独立做出来归并排序这块你基本过关了。最后再分享一个小细节刷题时不要只关注答案是否正确每次提交后看下耗时和内存的分布曲线归并排序的耗时通常应该在排序类题目的中上水平如果你明显偏慢检查一下是不是在递归里做了数组切片或者重复创建临时数组。这些细节才是刷题经验里最值钱的部分。