归并排序力扣题刷过一轮之后我最大的感受是它根本不是一道排序题而是一整套可以反复套用的分治框架。刚开始我在纯排序模板上花了不少时间直到用这套框架解掉逆序对计数和链表排序才明白为什么面试官总爱在归并排序上追问边界。这篇文章用实际题目串一遍归并的核心写法、四类高频变体和手写时最容易翻车的位置适合正在刷排序专题、或者觉得模板能背、换皮就卡壳的读者。把这几个变体彻底吃透归并这块也就算圆满收官了。1. 归并排序在力扣里的存在感比你想象中高得多先说结论归并排序在力扣里很少以请你写一个归并排序的形式出现除了第912题排序数组这种纯模板题它更多是藏在各种统计类题目的标准答案里。我整理了一下自己刷过的归并相关题目按考察方式可以分成四层分布。1.1 归并相关题目的四层分布第一层是纯排序第912题排序数组直接考察归并模板是否干净第二层是逆序对类统计合并左右两个有序段时顺手把跨区间的逆序对数量算出来时间复杂度仍然是 O(n log n)第三层是链表排序第148题排序链表要求 O(n log n) 的排序数组快排的随机访问思路在链表上施展不开而归并排序只需要顺序遍历加指针重接天然贴合链表结构第四层是区间统计比如第315题计算右侧小于当前元素的个数、第327题区间和的个数思路本质上还是分治后合并时做统计。题目考察重点归并扮演的角色912. 排序数组模板正确性标准分治排序数组中的逆序对经典题合并时计数跨区间逆序对统计148. 排序链表链表拆分与重接不依赖随机访问的排序315. 右侧更小元素个数索引跟踪合并过程累计答案327. 区间和的个数前缀和 双指针分治统计区间的数量1.2 统计类题目为什么绕不开归并这也是面试官和出题人都偏爱归并的原因它考察的不只是排序本身还有人是否真的理解递归拆分、索引边界、合并顺序这些底层细节。快排的模板可以背得很熟但归并的变体题一旦出现背模板和真理解立刻就能区分开。另外归并排序有一个快排没有的特性——稳定。合并时左右相等的情况必须先取左半边的元素这个细节在逆序对统计里直接影响答案正确性后面第2节我会专门讲。凡是你看到统计满足某种大小关系的数对数量且数对之间有天然的先后位置关系归并排序一般都在候选方案里。原因在于归并天然把数组分成左右两个区间而左区间的元素在原数组里全部位于右区间元素之前这正好是统计题需要的位置先后信息。2. 分治三步走先把不会错的基础归并写出来归并排序的递归写法非常固定先拆后合。拆的过程就是不断取中点把区间 [left, right] 切成 [left, mid] 和 [mid1, right]递归到只剩一个元素或者空区间为止。2.1 递归拆分的边界条件怎么写基础版本只有几行def merge_sort(nums, left, right): if left right: return mid (left right) // 2 merge_sort(nums, left, mid) merge_sort(nums, mid 1, right) merge(nums, left, mid, right)这里最容易出错的其实是两个细节。第一个是递归基我见过不少同学写成if left right: return这在当前写法的合法区间下不会出问题但如果后续把区间定义改成左闭右开left right就代表空区间逻辑就乱了。统一用left right更稳空区间和单元素区间都直接返回不用反复想边界。第二个是中点计算。Python 里(left right) // 2没有溢出问题但如果你用其他语言写更规范的写法是left (right - left) // 2。两个习惯一次养成后面切分任何二分区间都能少踩一个坑。拆完之后真正的核心在 merge 这一步——把两个已经各自有序的子数组合并成一个整体有序的数组这一步做对了归并就完成了百分之八十。2.2 merge 合并的双指针与临时数组合并的思路用生活场景说就是手里有两叠已经按顺序排好的扑克牌每次从两叠牌的最上面各取一张比大小小的先放进结果堆哪个牌堆空了就把另一堆剩下的直接倒进去。写成代码就是双指针def merge(nums, left, mid, right): temp [] i, j left, mid 1 while i mid and j right: if nums[i] nums[j]: temp.append(nums[i]) i 1 else: temp.append(nums[j]) j 1 while i mid: temp.append(nums[i]) i 1 while j right: temp.append(nums[j]) j 1 nums[left:right 1] temp几个容易看漏的细节第一个 while 的条件必须同时满足i mid和j right任意一个越界就要停下来靠后面两个 while 把剩余元素收尾。比较时用的是而不是。这个细节在纯排序里看似无所谓但在逆序对计数的题目里就是正确性问题相等元素不应该被算成逆序对如果你用等于就把相等元素错判了。最后整体写回原数组时区间必须是nums[left:right 1]。Python 切片左闭右开非常容易把right写成right - 1结果最后一个元素没写回去debug 到怀疑人生。2.3 为什么要用临时数组稳定排序的代价初学归并的人几乎都会问一个问题能不能不申请临时数组直接在原数组上做原地合并答案是能但代价很大。经典的原地合并做法是用循环旋转把两个有序段搬动整体时间复杂度会退化并且常数巨大更好的原地归并算法实现极其复杂面试和刷题场景下完全不划算。所以工程和竞赛的默认做法就是开一个 O(n) 的辅助数组用空间换简单和稳定。提示稳定排序的稳定二字指大小相等的元素在排序前后保持原来的相对顺序。归并能做到稳定关键就在于上面说的比较右半边元素只有严格小于左半边元素时才会被提前取出相等时永远先取左半边的这样左半边的元素一定排在右半边相等元素的前面。快排和堆排都不具备这个性质所以在需要稳定排序的实际场景里归并是默认候选之一。面试时主动把这一点讲出来比背一百遍模板都有说服力。3. 四类高频变体读懂题目是排序还是统计归并刷到后面你会发现题目表面上各不相同本质上都是在问同一个问题你能不能在合并两个有序段的过程中额外计算点什么。3.1 纯排序模板题先用第912题把框架跑通把上面merge_sort和merge两个函数原封不动提交到第912题排序数组能直接通过。但我建议不要只当作一次通过来对待而是把它当成归并模板对拍器每次改写归并逻辑之后先用这道题验证一遍排序结果是否正确再去做后面的统计变体。class Solution: def sortArray(self, nums: List[int]) - List[int]: n len(nums) temp [0] * n # 全局复用后面会讲为什么 def merge_sort(left, right): if left right: return mid (left right) // 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]: temp[k] nums[i] i 1 else: temp[k] nums[j] j 1 k 1 while i mid: temp[k] nums[i] i 1 k 1 while j right: temp[k] nums[j] j 1 k 1 nums[left:right 1] temp[left:right 1] merge_sort(0, n - 1) return nums这里我把 temp 数组提到外层统一创建而不是在 merge 里每次 new。原因后面第4节会专门算这笔账——在递归里反复分配临时数组小数据量时无所谓数据量到十万以上就会明显变慢。3.2 逆序对计数合并时顺手算出答案逆序对的定义是对于数组中的两个位置 i j如果 nums[i] nums[j]那么 (i, j) 就是一个逆序对。暴力解法是两层循环复杂度 O(n^2)数组长度到十万量级就跑不动了。归并的巧妙之处在于合并两个有序子数组时右半边的元素 j 每移动一次就说明它比左半边从当前位置 i 到 mid 的所有元素都小而左半边这些元素在原数组里都排在它前面。换句话说这时候一下子就发现了(mid - i 1)个逆序对。def merge_and_count(nums, temp, left, mid, right): i, j, k left, mid 1, left count 0 while i mid and j right: if nums[i] nums[j]: temp[k] nums[i] i 1 else: temp[k] nums[j] j 1 count mid - i 1 k 1 while i mid: temp[k] nums[i] i 1 k 1 while j right: temp[k] nums[j] j 1 k 1 nums[left:right 1] temp[left:right 1] return count关键就一行count mid - i 1。这行代码背后的逻辑是当右半边的 nums[j] 比左半边当前的 nums[i] 还小的时候左半边从 i 到 mid 的所有元素都比 nums[j] 大它们各自跟 nums[j] 都能组成一个逆序对因为它们在原数组里的位置都在 nums[j] 之前。于是不用逐个比较一次合并操作就能统计出一整批逆序对。举个例子数组 [3, 1, 2] 拆到最后左边是 [3]右边是 [1, 2]。合并时先把 1 取出来这时左边还剩 [3]1 比 3 小count 1再把 2 取出来左边还是 [3]2 比 3 小count 1。总共 2 个逆序对正好是 (3,1) 和 (3,2)。这个逻辑想清楚之后后面第315题的右侧更小元素个数就只是在同样的合并过程里把答案记录到每个原始下标上而已。3.3 链表排序把拆分改成快慢指针第148题排序链表是归并在链表场景下的经典变体。数组归并的拆分靠下标取中点链表没有随机访问只能用快慢指针找中点找到后把链表从中间断开递归排序两半最后再用常规的合并两个有序链表把结果接起来。def sort_list(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 sort_list(head) right sort_list(mid) return merge_two(left, right) def merge_two(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这个题最坑的地方在断链。slow走到中点后必须先把mid slow.next存下来再把slow.next置为None顺序反了就丢了后半段。我第一次写的时候是先置空再取mid结果递归进去全是空链表排序结果乱七八糟。另外注意链表归并的时间复杂度是 O(n log n)但递归深度 O(log n) 的栈空间不算 O(1)如果题目明确要求常数空间得改写成自底向上的迭代归并那是另一个难度层级先不展开。3.4 进阶第315题和第327题的统计答案套路第315题计算右侧小于当前元素的个数输出的是每个位置右侧有多少个比它小的元素。用归并做的思路是排序时不只记录值还记录每个元素原来的下标合并过程中每当右半边的元素被取出它前面的所有剩余左半边元素都比它大这些左半边元素各自对应的原下标都该 1。为了不重复累加常见做法是维护一个已经被取出多少右半边元素的计数器左半边元素被取出时把这个计数累加到它原下标的答案上。这个逻辑在纸上比划两遍就能懂但第一次写很容易把下标对应关系搞混。第327题区间和的个数是归并进阶题里比较硬核的一道先求前缀和数组问题就变成统计有多少对 (i, j) 满足lower prefix[j] - prefix[i] upper且 i j。对前缀和做归并排序时左右两个有序段分别是前缀和的前半部分和后半部分对于每个左段元素用两个指针在右段里圈出落在[prefix[i] lower, prefix[i] upper]范围内的元素个数。整个过程在合并的 merge 步骤里完成整体复杂度还是 O(n log n)。这两道题我建议放在前三种变体都写顺了之后再碰。它们本身很少作为面试第一题出现但一旦遇到能不能优化到 O(n log n)的追问归并统计的框架就是现成的答案。4. 手写归并的踩坑实录三个高频翻车点归并排序的代码行数不多但细节密度非常高。我统计了一下身边刷题的人问得最多的问题集中在三个位置。4.1 三个最常见的 bug 和排查方法第一个是递归切分区间写错。mid算出后右半区间起点必须是mid 1如果漏掉加 1两个子区间就会重叠递归会无限循环或者结果错乱。排查方法很简单在 merge 入口打一行日志打印left, mid, right对比相邻两层递归的区间是否能无缝覆盖。第二个是合并时比较符号用错。写排序模板时用没毛病但如果你在写逆序对计数时把改成来优化比较次数相等元素就会被错误地当成逆序对答案立刻偏大。记住一条原则统计逆序对的代码比较符号必须和排序模板保持一致也就是。第三个是临时数组的复用问题。很多人第一次写的 merge 里每次temp []递归到十几层之后建数组、扩容、垃圾回收的耗时远超排序本身。正确姿势是把 temp 数组提到外层长度和原数组一样合并时用下标覆盖写。我在第912题上实测过一千万量级数据下每次新建 temp 的版本耗时大约是复用版本的 1.5 到 2 倍这个差距在力扣的大数据用例上能明显感受到。4.2 常数优化小数组为什么该切插入排序归并排序递归到最底层时会处理大量长度为 1 或 2 的极小子数组。对这些小块走完整的递归和合并流程函数调用开销占比很高。工程上的标准做法是设定一个阈值通常是 16 或者 32小区间直接改用插入排序整体排序时间能明显下降。def hybrid_merge_sort(nums, left, right): if right - left 1 16: for i in range(left 1, right 1): key nums[i] j i - 1 while j left and nums[j] key: nums[j 1] nums[j] j - 1 nums[j 1] key return mid (left right) // 2 hybrid_merge_sort(nums, left, mid) hybrid_merge_sort(nums, mid 1, right) merge(nums, left, mid, right)这个优化的原理其实很简单插入排序在近有序和小规模数据上都很快而递归到深度 d 时每块大小是 n / 2^d当块小于阈值时插入排序的平方复杂度在常数极小的情况下完全能打过归并的递归开销。很多语言标准库里的排序内部就是这么干的只是阈值不同。刷题时如果追求极致速度可以把阈值调到 8 到 32 之间跑一遍对比如果只是想通过力扣用例不优化也完全够用。4.3 自测方法对拍器比脑内推理靠谱写算法题的调试方式我一直推荐对拍用随机数据反复生成输入把被测函数和标准实现的结果做比对。归并排序的标准实现就是 Python 内置的sorted()对拍逻辑几行就能写完import random for _ in range(1000): nums [random.randint(-100, 100) for _ in range(random.randint(0, 30))] original nums[:] merge_sort(nums, 0, len(nums) - 1) assert nums sorted(original), ffailed on {original}, got {nums}跑一万组随机用例都没挂你的模板基本就是稳的。除了随机数据还要手动补几个边界用例空数组、单元素数组、两个元素、所有元素相等、已经完全有序、完全逆序。这些用例成本极低但能覆盖掉绝大多数边界 bug。对拍器另一个好处是它能逼着你把函数签名和输入输出都规范化后面做变体题时直接改 merge 内部逻辑再用对拍器验证比在力扣上来回提交省时间多了。5. 归并思想还能怎么延伸从刷题到工程5.1 两道只考合并的送分题别放过第88题合并两个有序数组、第21题合并两个有序链表本质上就是归并排序里 merge 这个步骤的单独抽取。这两道题单独出现时都觉得很轻松但把它们和归并放在一起看才发现原来 merge 才是归并排序里最值钱的一步拆分只是辅助。把 merge 练到闭眼能写再面向对象地理解任意两个有序序列都能合并会慢慢形成一种条件反射——看到有序序列就想到用双指针合并看到无序序列就想先排序再合并。5.2 外部排序归并在真实场景里的主战场归并在刷题里是算法在工程里最经典的应用是外部排序。当数据量大到内存装不下时需要把数据分块读入、各自排序后写回磁盘生成多个有序片段然后用多路归并k-way merge把它们合并成一个完整有序的文件。这里用到的多路归并和力扣第23题合并 K 个升序链表的思路完全一致只是数据结构从链表换成了文件句柄选择最小元素用最小堆。我处理过类似的场景一份几个 GB 的日志文件需要按时间戳排序单机内存有限当时就是拆块排序外加小顶堆做多路归并把单机排序跑完了。这种场景下归并排序的顺序访问特性特别重要——它不需要随机跳到文件任意位置天然契合磁盘的连续读特性快排那套随机访问在磁盘上会慢到没法看。5.3 面试中讲归并的两个加分点最后聊聊面试表达。被问到归并排序时大部分人的回答是先分再合复杂度 O(n log n)这没错但不出彩。我听过不少面试回答有两个加分点值得主动讲。第一主动提稳定性。当被问到归并和快排的区别时不要只说复杂度补一句归并稳定、快排不稳定归并需要 O(n) 额外空间快排是原地排序但最坏 O(n^2)信息量立刻就上来了。第二主动讲为什么归并能统计逆序对。你能把合并时count mid - i 1的道理讲清楚说明你不是背模板而是理解了左半边元素全部位于右半边元素之前这个关键性质。面试官如果再追问第315题的同构问题你就能顺着同样思路给出答案。归并排序的代码量不大但它是一个非常典型的10 行代码、1 万个细节的题。把上面几个翻车点亲手踩一遍、再跑一遍对拍器你会发现自己对分治的理解会上一个台阶。之后再看第315题和第327题就不再是这道题怎么做而是它到底在问归并的哪个步骤了。