企业官网建设流程全解析

归并排序力扣题刷过一轮之后，我最大的感受是：它根本不是一道"排序题"，而是一整套可以反复套用的分治框架。刚开始我在纯排序模板上花了不少时间，直到用这套框架解掉逆序对计数和链表排序，才明白为什么面试官总爱在归并排序上追问边界。这篇文章用实际题目串一遍归并的核心写法、四类高频变体和手写时最容易翻车的位置，适合正在刷排序专题、或者觉得"模板能背、换皮就卡壳"的读者。把这几个变体彻底吃透，归并这块也就算圆满收官了。

1. 归并排序在力扣里的存在感，比你想象中高得多

先说结论：归并排序在力扣里很少以"请你写一个归并排序"的形式出现（除了第912题"排序数组"这种纯模板题），它更多是藏在各种统计类题目的标准答案里。我整理了一下自己刷过的归并相关题目，按考察方式可以分成四层分布。

1.1 归并相关题目的四层分布

• 第一层是纯排序，第912题"排序数组"直接考察归并模板是否干净；
• 第二层是逆序对类统计，合并左右两个有序段时顺手把跨区间的逆序对数量算出来，时间复杂度仍然是 O(n log n)；
• 第三层是链表排序，第148题"排序链表"要求 O(n log n) 的排序，数组快排的随机访问思路在链表上施展不开，而归并排序只需要顺序遍历加指针重接，天然贴合链表结构；
• 第四层是区间统计，比如第315题"计算右侧小于当前元素的个数"、第327题"区间和的个数"，思路本质上还是"分治后合并时做统计"。

1.2 统计类题目为什么绕不开归并

这也是面试官和出题人都偏爱归并的原因：它考察的不只是排序本身，还有人是否真的理解递归拆分、索引边界、合并顺序这些底层细节。快排的模板可以背得很熟，但归并的变体题一旦出现，"背模板"和"真理解"立刻就能区分开。

另外，归并排序有一个快排没有的特性——稳定。合并时左右相等的情况必须先取左半边的元素，这个细节在逆序对统计里直接影响答案正确性，后面第2节我会专门讲。凡是你看到"统计满足某种大小关系的数对数量"，且数对之间有天然的先后位置关系，归并排序一般都在候选方案里。原因在于归并天然把数组分成左右两个区间，而左区间的元素在原数组里全部位于右区间元素之前，这正好是统计题需要的"位置先后"信息。

2. 分治三步走：先把不会错的基础归并写出来

归并排序的递归写法非常固定：先拆后合。拆的过程就是不断取中点，把区间 [left, right] 切成 [left, mid] 和 [mid+1, 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), f"failed 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题，就不再是"这道题怎么做"，而是"它到底在问归并的哪个步骤"了。