如果只让挑一种排序算法来啃,我会选归并排序。它不只是能排序,更是一把分治的钥匙——力扣上很多看起来和“排序”八竿子打不着的题,比如逆序对、区间和的个数,本质都是借归并排序的合并过程做统计。想把这些题吃透,第一件事就是把归并排序的原理、模板和变体一次性理清。这篇文章写给两类人:一是刚接触分治、想把归并排序写熟练的入门读者,二是已经在刷力扣中等题、但总在“知道要用归并却套不上题”的进阶读者。我会从最基础的合并两个有序数组讲起,逐步拆到排序链表、逆序对这一类高频题,最后把我在调试中反复踩过的坑和排查方法整理成速查清单。1. 归并排序为什么值得专门刷1.1 一次合并两个有序数组,是很多题的起手式归并排序的核心操作,说白了就是把两个已经各自有序的数组合并成一个大的有序数组。这个动作如果你单独练习过,就会觉得特别生活化:两叠已经按学号排好的试卷,你想把它们合成一叠,只需要每次比较两叠最顶上那张的学号,把小的那张放到新一叠里,直到某一叠空了,再把剩下那叠直接接上去。这个“比较头部、取走较小者”的过程,就是归并里的 merge 操作。力扣上的经典题“合并两个有序数组”,其实就是把这个 merge 动作单独拎出来考,只不过用了从后往前填充的优化。先把这个动作练熟,后面写完整的归并排序会顺手很多。从刷题角度看,归并排序值得作为重点研究对象,是因为它的 merge 过程可以被“加料”。排序本身只是整理数据,但如果你在合并两个有序区间时,额外比较一下左右区间的元素关系,就能顺手统计出逆序对、区间和个数等答案。这就是归并排序区别于快排、堆排的最大优势——它天然保留了元素之间跨区间的相对关系,做题时非常容易扩展。1.2 稳定、确定的复杂度,让归并在笔试里很稳归并排序的时间复杂度是严格的 O(n log n),无论数据原来是升序、降序还是完全乱序,都不会退化。这一点比快速排序更让人安心。快排虽然平均也是 O(n log n),但在极端的倒序输入下,如果选基准的策略不好,会退化到 O(n²),笔试里一旦遇到构造过的数据就会超时。而归并排序每次都对半划分,递归深度固定为 log n 层,每层合并的总代价是 O(n),整体就是 O(n log n)。同时归并排序是稳定排序。稳定意味着如果两个元素值相等,排序后它们的前后顺序不会变。对数组本身来说这个性质好像无所谓,但对结构体排序、按多个关键字排序的场景就很重要。而且在某些力扣题目里,稳定性能保证统计不重不漏,比如逆序对题里,左半区间和右半区间元素相等时,我们选择先取左半,才能保证不会把相等的元素误判成逆序对。1.3 归并排序和其他排序的选择差异用一句容易记住的话来区分:快排是“先大体分好,再递归细排”,归并是“先递归切到最小,再一路合并上来”。这个差异直接决定了它们适用的场景。数组排序:快排通常更快,因为缓存局部性好;归并需要额外 O(n) 空间。链表排序:归并排序几乎是无脑首选,因为链表不支持随机访问,快排找基准和分区都需要来回遍历,而归并只需要顺序访问节点。需要稳定排序:归并优于快排。需要借排序过程统计信息:归并优于一切比较排序,因为合并时左右区间都在手边,可以顺便算。我在实际做题中的体会是,单纯排序题用语言内置的排序函数就够了,但一旦题目要求自己实现排序,或者要求 O(n log n) 且不能用额外太多空间时,归并往往才是合理的答案。2. 手写归并的核心模板与细节2.1 递归终止条件怎么定手写归并排序,第一步是把递归的终止条件写对。我见过不少新手在这里翻车,最常见的是把条件写成if len(nums) 1就返回。这种写法在切片版里能用,但在原数组 左右边界的版本里会漏掉空区间的情况。更稳妥的写法是:if l r: return这段代码的意思是:当左边界大于等于右边界时,说明当前区间要么是空区间,要么只有一个元素,这两种情况都不需要再排序,直接返回。只有从“区间长度至少为 2”的节点才需要继续切分和合并。这里还有一个隐藏细节:mid 的计算。通常写成mid (l r) // 2,但在 C 等语言里,为了安全可以写成mid l (r - l) // 2,防止 l r 溢出。Python 不用太担心溢出,但养成这个习惯没坏处。切分的时候,左区间是[l, mid],右区间是[mid 1, r],一定要保证左右区间不重叠、不遗漏。2.2 merge 时临时数组为什么要复用合并两个有序区间时,我们需要一个临时数组来存放合并结果。很多初学者会写成在每次递归的 merge 里新建一个列表:res []这样写逻辑没错,但代价是:每一层递归都会新建数组,递归深度是 log n 层,每层有多个节点,整体会频繁触发内存分配,性能明显变差。力扣的测试数据规模通常能到几十万,这么做很容易超时或内存飙升。更工程化的做法是,在整个排序开始前开一个长度为 n 的临时数组,然后在合并过程中反复使用。这也是面试时比较容易加分的点。因为归并排序的整体额外空间是 O(n),如果你在每一层都新建数组,虽然复杂度仍然是 O(n),但常数项要大得多,而且会给面试官一种“你不太懂空间复用”的印象。2.3 可直接背下的递归归并模板下面这个模板是我在力扣题里最常用的版本,它直接在原数组上排序,全程复用一个 tmp 数组。核心逻辑集中在 sort 和 merge 两个函数里。class MergeSort: def sort(self, nums): self.tmp [0] * len(nums) self.merge_sort(nums, 0, len(nums) - 1) def merge_sort(self, nums, l, r): if l r: return mid (l r) // 2 self.merge_sort(nums, l, mid) self.merge_sort(nums, mid 1, r) # 合并两个有序区间 i, j, pos l, mid 1, l while i mid and j r: if nums[i] nums[j]: self.tmp[pos] nums[i] i 1 else: self.tmp[pos] nums[j] j 1 pos 1 while i mid: self.tmp[pos] nums[i] i 1 pos 1 while j r: self.tmp[pos] nums[j] j 1 pos 1 nums[l:r1] self.tmp[l:r1]注意最后一个回写动作nums[l:r1] self.tmp[l:r1],这行非常关键。如果你只往 tmp 里放数据,却不回写原数组,那么上一层合并时拿到的两个子区间仍然是无序的,整个排序就会失效。很多人调试半天找不到问题,最后发现就是漏了这行或者回写的边界写错。2.4 自底向上写法:省递归,但边界更碎递归版的归并排序好理解,但 Python 的递归深度默认限制在一千左右,虽然力扣的数组规模通常不会导致递归爆栈,但如果你追求稳妥,或者面试时被要求写成迭代版,可以试试自底向上归并。自底向上的思路是:先把数组看成 n 个长度为 1 的有序区间,然后两两合并成长度为 2 的区间,再合并成长度为 4 的区间,直到整个数组有序。def merge_sort_iterative(nums): n len(nums) tmp [0] * n length 1 while length n: for left in range(0, n, 2 * length): mid min(left length - 1, n - 1) right min(left 2 * length - 1, n - 1) if mid right: continue # 合并 nums[left:mid] 和 nums[mid1:right] i, j, pos left, mid 1, left while i mid and j right: if nums[i] nums[j]: tmp[pos] nums[i] i 1 else: tmp[pos] nums[j] j 1 pos 1 while i mid: tmp[pos] nums[i] i 1 pos 1 while j right: tmp[pos] nums[j] j 1 pos 1 nums[left:right1] tmp[left:right1] length * 2这段代码里最需要注意的是每个区间的末尾可能不满一段,所以 mid 和 right 都要用 min 截断。我在初学迭代归并时,跳出循环的条件一旦写成length n//2,在数组长度不是 2 的幂时就会漏掉最后的合并段。稳妥的写法就是while length n,让最后一次合并一定能覆盖整个数组。3. 力扣里最常见的四类归并题型3.1 纯排序题:先验证模板手不手生我并不建议你完全用内置 sort 函数去刷所有排序题,因为力扣中有些题目是明确要求手写排序的。归并排序最适合用来做的第一类题,就是你打算测试模板是否熟练的“排序数组”题。这类题看起来简单,实际上是个很好的自检机会。写的时候,你只需要把上面的模板原封不动搬上去,然后注意以下几点:数组为空或长度为 1 时,程序能不能直接返回。临时数组开多大,是不是等于原数组长度。回写时切片边界对不对。我见过太多人在这些细节上翻车。比如临时数组长度开成n 1,结果回写时越界;或者递归终止条件写成l r,一旦传入空数组就直接出错。这类题不需要奇技淫巧,就是考察你基础功扎不扎实。3.2 排序链表:归并把空间复杂度降下来链表排序是归并排序非常经典的应用场景。数组归并需要额外 O(n) 空间,但链表归并在合并时只需要修改指针,不需要额外的数据结构空间,所以整体额外空间复杂度可以做到 O(log n),这里的 log n 主要来自递归调用栈。如果题目明确要求常数级额外空间,那就需要把递归版改成自底向上迭代版。链表归并排序的框架和数组版几乎一样,但有两个点需要特别处理:找链表中点,要使用快慢指针。把链表从中间断开,通常用slow.next None,让递归处理左半段时不会串到右半段。这里给出一个递归版链表排序的参考代码。class Solution: def sortList(self, 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 left self.sortList(head) right self.sortList(mid) return self.merge(left, right) def merge(self, l1, l2): dummy ListNode(0) cur dummy while l1 and l2: if l1.val l2.val: cur.next l1 l1 l1.next else: cur.next l2 l2 l2.next cur cur.next cur.next l1 if l1 else l2 return dummy.next快慢指针这个写法,fast要先指向head.next,而不能和slow都指向 head。否则偶数长度链表找中点时,slow 会落在中间偏左的位置,截断后左右长度不平衡,虽然递归仍能正确排序,但容易多走一层,不够干净。把fast停在head.next,当链表长度为偶数时,中点恰好是前半段的最后一个节点,合并出来的结果更均衡。我在刷链表题时,每次用快慢指针都会在纸上画一遍:长度为 4 的链表,slow 应该停在第 2 个节点,fast 应该走到 None;长度为 5 的链表,slow 停在第 3 个节点,fast 停在最后一个节点。画几遍以后,这个边界问题基本就不会再出错了。3.3 逆序对:归并过程中顺手统计答案逆序对这个题,可能是归并排序所有应用里最有代表性的。题目定义很简单:数组里有多少对 (i, j),满足 i j 且 nums[i] nums[j]。暴力做法是两层循环,复杂度 O(n²),数据规模一大必然超时。而用归并排序可以把复杂度降到 O(n log n),因为归并过程中,左右两个子区间分别有序,跨区间的逆序对能被一次合并统计出来。具体逻辑是这样:合并左边区间[l, mid]和右边区间[mid1, r]时,如果发现nums[j] nums[i],那么左边区间里从 i 到 mid 的所有元素都大于 nums[j],这些元素和 nums[j] 都构成逆序对。因此,逆序对数量可以直接加上mid - i 1。class Solution: def reversePairs(self, nums): self.cnt 0 self.tmp [0] * len(nums) self.merge_sort(nums, 0, len(nums) - 1) return self.cnt def merge_sort(self, nums, l, r): if l r: return mid (l r) // 2 self.merge_sort(nums, l, mid) self.merge_sort(nums, mid 1, r) i, j, pos l, mid 1, l while i mid and j r: if nums[i] nums[j]: self.tmp[pos] nums[i] i 1 else: self.tmp[pos] nums[j] j 1 self.cnt mid - i 1 pos 1 while i mid: self.tmp[pos] nums[i] i 1 pos 1 while j r: self.tmp[pos] nums[j] j 1 pos 1 nums[l:r1] self.tmp[l:r1]这段代码里最值得注意的地方是,统计必须发生在合并过程中,而不是排序完成后再统计。因为合并完成之后,左右区间的元素已经混在一起,原有的跨区间顺序信息就丢失了。这也是归并排序应用的核心思想:利用合并过程中“左右区间仍然相对有序”的窗口期,把额外信息收集出来。还有一个经典的易错点:当nums[i] nums[j]时,使用小于等于而不是小于。如果写成小于,排序仍然正确,但相等元素会被错误地计为逆序对。因为归并排序是稳定排序,相等的元素不应该被交换,自然也不应该进入逆序对计数。这个坑我至少见人踩过三次,每次都是排查到最后才发现等号丢了。3.4 区间和的个数:把前缀和放进归并框架区间和的个数是归并排序另一道经典难题。它要求统计有多少个子数组的和落在[lower, upper]范围内。直接枚举所有子数组需要 O(n²),但如果把子数组和转换成前缀和之差,就能用归并排序的分治结构来加速。具体思路是这样的:先算出前缀和数组 pre,pre[i] 表示原数组前 i 个元素的和。任意子数组[i, j]的和等于pre[j1] - pre[i]。所以问题变成:统计有多少对下标位置 i, j,满足 i j 且pre[j] - pre[i]在给定范围内。看到“下标位置 i j 且满足某个差值条件”,你应该马上联想到逆序对的套路。我们可以对前缀和数组做归并排序,在合并左右两个有序区间时,针对左半区的每个元素 pre[i],找右半区里有多少个 pre[j] 满足:pre[i] lower pre[j] pre[i] upper因为左右两个区间都已经有序,右半区可以用两个指针分别维护满足下限和上限的边界。左半区指针向右移动时,这两个边界指针也只会向右移动,整个合并过程中统计的总代价是 O(n),不会变成 O(n²)。每一层归并做 O(n) 统计,整体复杂度就保持在 O(n log n)。这道题给我的最大启发是:归并排序不仅能处理“排序”这件事,还能在排序过程中把元素按值域分成两半,然后快速回答某种“区间内有多少个”的计数问题。逆序对统计的是简单的偏序关系,区间和的个数统计的是落在数值区间里的数量,本质思路一脉相承。4. 从套模板到灵活改写的实操过程4.1 第一步:先把模板练到闭眼能写我建议你找一个没有代码提示的文本编辑器,把自己的归并模板默写三遍以上。第一遍对照着理解,第二遍尝试独立写,第三遍限时五分钟内写完。这个过程听起来很笨,但在真正面试或笔试时,归并排序常常只是整道题的中间步骤。如果模板不够熟,你在递归边界和回写顺序上多花三分钟,后面整个思路就会被搅乱。默写的时候,重点检查三个位置:递归终止条件、mid 的计算、合并后回写原数组。这三个位置只要有一个出错,程序基本跑不对。我自己的习惯是,把模板写成“三段式”:先递归处理左右,再合并,最后回写。这样结构清晰,不容易漏。4.2 第二步:给模板加一个“统计回调”模板写熟以后,下一步是练习在 merge 过程中插入额外逻辑。最好的练手题就是逆序对。你可以先自己写出原版归并,然后在 else 分支里加一行统计:self.cnt mid - i 1加这一行之前,先问自己几个问题:为什么是在nums[j] nums[i]时触发?为什么加的是mid - i 1而不是其他数?如果数组里有重复元素,统计会不会被破坏?这些问题能答上来,说明你对归并过程的理解已经过关了。同理,区间和的个数这道题也可以看成是给归并模板加了一个“区间计数回调”:在真正合并左右区间之前,先扫描一遍右半区,统计满足条件的元素个数。统计完成后,再走正常的合并流程。这里的统计和排序互不干扰,因为统计使用的仍是合并前的有序状态。4.3 第三步:把数组版改成链表版数组版和链表版看似是两个模板,其实就是同一个分治思想在不同数据结构上的体现。从数组版迁移到链表版时,重点不是背代码,而是理解三个差异:链表没有随机访问,所以找中点要用快慢指针。链表不需要临时数组,合并时构造辅助头节点 dummy 即可。链表递归版的空间复杂度只有 O(log n),数组递归版是 O(n)。如果你有时间,可以尝试把自底向上归并也写成链表版。这个版本在链表排序的“常数空间”要求下很有用。它的核心思路是:先按长度为 1 的段两两合并,再按长度为 2 的段两两合并,直到整个链表有序。写起来比数组版复杂,但能极大提升你对链表操作的熟练度。4.4 第四步:复杂度和内存的取舍记录每次写完一个归并相关的题,我都会在题解旁边记录一组复杂度数据,格式大概是:时间复杂度:每一层归并 O(n),共有 log n 层,总 O(n log n)。空间复杂度:数组版需要额外 O(n) 的临时数组;链表递归版需要 O(log n) 栈空间;链表迭代版可以做到 O(1)。稳定性:相等元素不交换顺序,稳定排序。这些数据在面试里几乎是必问的。尤其是空间复杂度,很多人只记得归并排序“需要额外空间”,却说不清数组版和链表版的区别。如果你能主动说“数组版 O(n),链表递归版 O(log n),链表迭代版 O(1)”,面试官一般会认为你真的理解了这个算法。5. 常见问题与排查技巧实录5.1 边界条件错位,排查半小时起步我把刷归并题时遇到过的高频边界问题整理成一个速查表,方便你对照。症状常见原因排查办法排序后数组大部分有序,但中间夹杂错乱元素合并后没有回写原数组,或者回写区间算错检查nums[l:r1] tmp[l:r1],确认 l 和 r 一致递归无限循环mid 计算导致左区间没有缩小检查是否写成mid (l r) // 2,并且递归处理[l, mid]与[mid1, r]空数组或长度为 1 时报错终止条件只写了l r,没有处理l r改成if l r: return逆序对结果偏小统计逻辑放在合并完成之后把cnt mid - i 1放在 else 分支的合并过程中逆序对结果包含相等元素比较条件写成改成这些错误如果你靠肉眼盯着代码找,效率很低。我后来学到一个好方法是“打点法”:在递归函数的开头打印 l 和 r,在 merge 后打印数组的当前区间。只要输出里出现了l r但程序没有及时返回,就能立刻定位到终止条件的问题。5.2 临时数组索引和回写顺序数组版归并最容易出问题的细节,是临时数组的索引位置。初学者容易写成这样:tmp[i] nums[j] # 错, i 是左指针,不是写入位置正确写法里,写入位置 pos 和遍历指针 i、j 是三个不同的变量。pos 记录的是当前合并结果应该写到 tmp 的哪个位置,它的初始值是 l,而不是 0。如果写成从 0 开始,那么 tmp 数组的前面会被重复覆盖,后面的数据没有及时更新,回写时就会把错误的顺序写回原数组。还有一个容易忽略的点:回写原数组时,nums[l:r1] tmp[l:r1]这个切片操作在 Python 里是安全的,但如果底层语言不支持切片,你需要写一个循环:for k in range(l, r 1): nums[k] tmp[k]我建议即使你在 Python 里刷题,也要理解这个循环版本,因为有些在线评测环境里,切片复制会有额外开销,改成循环有时反而更快。5.3 用随机数组当对数器排查归并排序的问题,最高效的工具是“对数器”。解释一下,对数器就是一个能生成大量随机测试用例、并用暴力算法验证正确性的自检工具。对排序算法来说,对数器可以长这样:import random def brute_force_sort(nums): return sorted(nums) def test_merge_sort(times1000): for _ in range(times): n random.randint(0, 20) nums [random.randint(-10, 10) for _ in range(n)] expected brute_force_sort(nums[:]) # 假设你的归并排序是在 nums 原数组上排序 obj MergeSort() obj.sort(nums) if nums ! expected: print(出错了, nums, expected) return False return True对数器最大的价值,不是验证你已经会写的正确代码,而是在你改写模板加统计逻辑时,及时发现数据被排序过程改乱了。比如写逆序对时,你可以先用对数器确认排序本身仍然正确,再单独写一个 O(n²) 的暴力统计结果和归并统计结果比对。两道关卡都过了,代码基本就稳了。5.4 逆序对题的经典翻车场景逆序对这道题,我见过好几种翻车方式,这里挑三个典型的讲。第一个是变量作用域的问题。用 Python 写类方法时,如果计数变量cnt没有加self,只在局部作为普通变量,那么每次递归调用时它都会被重新初始化为 0,最终返回的统计永远是 0。这个错误非常隐蔽,因为排序还是正确的,只是统计没有累加上去。第二个问题是在合并前忘记先递归。有些新手图省事,直接在整个数组上做一次 merge,然后统计出来的跨区间逆序对只包含最外层的,漏掉了左右区间内部的逆序对。归并排序的递归顺序一定是“先递归,再合并”,统计跨区间逆序对的前提是左右区间内部已经递归完成并且统计完毕。第三个问题是统计和排序互相干扰。如果你先排序再统计,左右区间一旦合并,原来跨区间的相对顺序就没了,统计结果一定会错。所以正确的设计是在合并代码的 else 分支里同时完成“排序动作”和“统计动作”,让它们共享同一次遍历。一点个人体会归并排序是我刷分治类题目时收获最大的一类模板。它真正值钱的地方,不是能把一个数组排成升序,而是提供了一种极其规整的“把数组对半切开,再逐个区间处理”的思考框架。我后来遇到合并区间、寻找中位数、区间计数这些题,第一反应都会想:能不能用分治,能不能在归并过程中顺手多做一点事。如果你现在正处于刷题瓶颈期,不妨把归并排序当成突破口。先把模板背下来,再把逆序对和排序链表两道题各写三遍,你会发现后面再看其他分治题,思路会开阔很多。最后分享一个小技巧:每次写完归并相关代码,都顺手在注释里写下三个数——l、mid、r分别代表什么,以及回写的时候为什么是这个边界。别小看这三行注释,它们能帮你把最容易出错的区间问题彻底钉死在脑子里。