归并排序在力扣里是个很特别的存在。你说它是基础题吧，直接让你背模板的题确实不多；但你说它是冷门算法吧，一到中等偏上的题，比如逆序对、排序链表、区间和统计，归并排序的思路几乎无处不在。很多同学刷到“排序数组”这类题时，觉得归并排序就是两种写法选一种背下来就行；等到刷“计算右侧小于当前元素的个数”时，才发现自己压根没理解归并排序的合并过程到底在干什么。这篇文章我想把归并排序从力扣入门模板题到高阶变形题的完整链路拆开讲清楚，适合刚开始刷排序题的新手，也适合那些能把归并排序代码默写出来、但一变型就卡壳的进阶选手。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] 和 [mid+1, 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] 和 [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 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]和[mid+1, 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指向2，j指向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 = head，fast = 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:mid+1]这种切片，每层递归都会复制一次数组，空间复杂度直接爆炸。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的数组的完整归并过程，写在纸上，这一步决定你是否真的理解了递归展开。第二步，按顺序刷排序数组、数组中的逆序对、排序链表，每道题都自己重新默写代码，不要复制粘贴。第三步，把三个版本的代码放在一起对比，找出它们的共同骨架和差异点，这个过程能帮你建立“分治合并”的思维模板。第四步，挑战计算右侧小于当前元素的个数，如果你能独立做出来，归并排序这块你基本过关了。最后再分享一个小细节，刷题时不要只关注答案是否正确，每次提交后看下耗时和内存的分布曲线，归并排序的耗时通常应该在排序类题目的中上水平，如果你明显偏慢，检查一下是不是在递归里做了数组切片或者重复创建临时数组。这些细节才是刷题经验里最值钱的部分。
归并排序在力扣里是个很特别的存在。你说它是基础题吧，直接让你背模板的题确实不多；但你说它是冷门算法吧，一到中等偏上的题，比如逆序对、排序链表、区间和统计，归并排序的思路几乎无处不在。很多同学刷到“排序数组”这类题时，觉得归并排序就是两种写法选一种背下来就行；等到刷“计算右侧小于当前元素的个数”时，才发现自己压根没理解归并排序的合并过程到底在干什么。这篇文章我想把归并排序从力扣入门模板题到高阶变形题的完整链路拆开讲清楚，适合刚开始刷排序题的新手，也适合那些能把归并排序代码默写出来、但一变型就卡壳的进阶选手。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] 和 [mid+1, 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] 和 [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 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]和[mid+1, 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指向2，j指向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 = head，fast = 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:mid+1]这种切片，每层递归都会复制一次数组，空间复杂度直接爆炸。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的数组的完整归并过程，写在纸上，这一步决定你是否真的理解了递归展开。第二步，按顺序刷排序数组、数组中的逆序对、排序链表，每道题都自己重新默写代码，不要复制粘贴。第三步，把三个版本的代码放在一起对比，找出它们的共同骨架和差异点，这个过程能帮你建立“分治合并”的思维模板。第四步，挑战计算右侧小于当前元素的个数，如果你能独立做出来，归并排序这块你基本过关了。最后再分享一个小细节，刷题时不要只关注答案是否正确，每次提交后看下耗时和内存的分布曲线，归并排序的耗时通常应该在排序类题目的中上水平，如果你明显偏慢，检查一下是不是在递归里做了数组切片或者重复创建临时数组。这些细节才是刷题经验里最值钱的部分。