企业官网建设流程全解析

整理力扣刷题笔记时看到这个标题，我愣了一下：“归并排序力扣题（leetcode）萍”。那个“萍”字大概是哪回一时手滑打上去的，后来忘了删。但恰恰是这种残缺的随记，让我想起一个绕不开的问题：归并排序到底难在哪？

背过模板的人可能觉得不难，甚至觉得它“有点过时”——毕竟工程上很少手写归并，各语言内置排序又快又稳。可是你看力扣上的题：912 排序数组、剑指 Offer 51 数组中的逆序对、315 计算右侧小于当前元素的个数、148 排序链表，难度从中等到困难，覆盖面从纯排序到分治统计。没有一题是靠死记模板能过关的，每一题都得真正理解“分治+合并”这个动作在想什么。

这篇文章想聊的，就是归并排序从模板到变式的完整刷题路线。准备面试的可以按这个顺序过一遍，刷逆序对类题目卡住的可以重点看中间部分，连递归边界都没想明白的，建议从基础模板开始读。我会把原理、代码、踩坑过程都摊开讲，没有花哨技巧，都是能直接搬走的东西。

1. 我为什么还在翻来覆去写归并排序：从标题里的“萍”说起

1.1 人人能背模板，但一到变式就懵

归并排序可能是“看起来最没有神秘感”的排序算法。教科书上说得很简单：分两半，分别排序，再合并。代码也就二十来行，不少人都能默写出来。

可真到刷题的时候，问题就来了。912 排序数组，要求手写排序，有人能写出来，可追问一句“为什么合并时要用临时数组？能在原数组上原地归并吗？”就卡壳了。到了 315 这种标着“困难”的题，更是完全没法把模板套上去。

我见过不少同学，基础模板背得滚瓜烂熟，一碰到“统计某个元素右侧有多少比它小的数”就懵。他们最大的障碍不是不会写代码，而是没有把归并的合并阶段当成一个“可以顺路计数”的过程。这一点想通了，逆序对、翻转对、区间和这些题全都变成了同一个套路。

1.2 归并在力扣上的出题密度，比想象中高

随手整理一下归并相关题目，你会发现它不是“冷门考点”，而是分治思想最重要的载体之一。

看到没有？困难题占比不小。而且这些题有一个共同特征：如果没意识到“归并可以在排序过程中附带信息”，你会觉得它们和排序八竿子打不着，只会去套树状数组、线段树。会归并的人则能在考场里多一条非常朴素的路。

1.3 这篇文章的刷题路线

我推荐的顺序是：先把基础模板敲到闭眼能写，然后理解递归树上的每一次合并，再进入逆序对类题目，最后练链表版。别一上来就刷 315，那样除了挫败感什么都得不到。

接下来每一步我都会给出可运行的代码，并且解释“为什么这么写”。很多人写了十年归并，却不知道某些边界条件为什么是那样的，正好借这篇文章把账算清楚。

2. 分治的递归树：把归并排序的骨架画进脑子里再动手

2.1 递归的终止条件与 mid 边界：别小看那两行

归并排序的核心动作是“合并两个有序部分”，但要让这个动作成立，得先递归地把数组拆成长度为 1 的区间。一个元素自然是有序的，这就是递归的底。

def merge_sort(nums, left, right): if left >= right: return mid = left + (right - left) // 2 merge_sort(nums, left, mid) merge_sort(nums, mid + 1, right) # 到这里，nums[left:mid+1] 和 nums[mid+1:right+1] 已经各自有序 merge(nums, left, mid, right)

这里有两个细节值得较真。第一，终止条件是left >= right而不是left == right，因为递归调用里可能出现left > right吗？不会，但写上>=能让函数更健壮，也和你写其他分治题的惯用写法统一。第二，mid = left + (right - left) // 2比(left + right) // 2多写几个字符，换来的是大数组下不会溢出的安全性。Python 整数不溢出，但 Java、C++ 里这是面试官爱挖的坑，习惯要从现在养成。

2.2 合并的完整过程：双指针整理“最小有序单元”

合并这段是归并排序的灵魂。打个比方：你手上有两堆扑克牌，每堆都从小到大排好了，现在要合成一堆。你每次只需要看两堆最上面的牌，把小的拿走。重复这个动作，直到某一堆空了，再把另一堆剩下的全部放上去。

代码也是这样：

def merge(nums, left, mid, right): tmp = [] i, j = left, mid + 1 while i <= mid and j <= right: if nums[i] <= nums[j]: tmp.append(nums[i]) i += 1 else: tmp.append(nums[j]) j += 1 while i <= mid: tmp.append(nums[i]) i += 1 while j <= right: tmp.append(nums[j]) j += 1 nums[left:right + 1] = tmp

有几个点必须想明白，否则变式题会踩坑。

为什么需要一个tmp？因为归并不是“交换相邻元素”，而是跨区间搬移。如果直接在原数组上归并，需要额外的指针移动技巧，复杂度会变得非常高，或者干脆不稳定。用一个临时数组把结果攒好，再整体写回，是最朴素也最不容易出错的做法。

为什么两个 while 循环要把剩下的元素全部接上？因为第一轮while i <= mid and j <= right退出时，可能是左边用完了，也可能是右边用完了。你没用完的那一侧，剩余元素一定不小于已经写入的所有元素，所以直接整体追加即可。这个动作看似简单，漏掉它整个排序就废了。

2.3 复杂度与稳定性：面试官最爱追问的三个点

归并排序复杂度是稳定的 O(n log n)，无论数据原本什么样，递归树都是平衡的。空间复杂度 O(n)，来源就是每层合并时创建的临时数组，总峰值是最后一层合并时的 O(n)。

稳定性是一个容易被忽略的点。nums[i] <= nums[j]这个“等于号”不是可有可无的。如果写成<，当左右两半出现相等元素时，右侧元素会先被取走，原本靠前的相等元素反而被换到后面，排序就变得不稳定。

你可能觉得“不稳定怕什么？排序数字又不看顺序”。但在逆序对类题目里，稳定性直接影响统计结果——我们依赖“相等元素不产生逆序对”这个前提做计数。所以基础模板里的等于号，背后是数学上的严谨性，别乱动。

3. 先过几道基础关：912、215 与剑指 Offer 51 的取舍思路

3.1 912 排序数组：一份能直接提交的模板

912 是力扣上最直白的手写排序题。用归并排序就是一把梭：上面的模板直接提交就能过。这里真正值得练的不是“写对”，而是“写得快且能讲清楚”。

我推荐把排序函数拆成merge_sort和merge两个方法，不要糅在一起。原因有两个：一是面试时你拆开讲“分治”和“合并”两个阶段会很清晰；二是后面做逆序对变式题时，改动的只会在合并阶段，拆分结构能让你专注改一处。

class Solution: def sortArray(self, nums: List[int]) -> List[int]: self.nums = nums self.merge_sort(0, len(nums) - 1) return nums def merge_sort(self, left, right): if left >= right: return mid = left + (right - left) // 2 self.merge_sort(left, mid) self.merge_sort(mid + 1, right) self.merge(left, mid, right) def merge(self, left, mid, right): tmp = [] i, j = left, mid + 1 while i <= mid and j <= right: if self.nums[i] <= self.nums[j]: tmp.append(self.nums[i]) i += 1 else: tmp.append(self.nums[j]) j += 1 while i <= mid: tmp.append(self.nums[i]) i += 1 while j <= right: tmp.append(self.nums[j]) j += 1 self.nums[left:right + 1] = tmp

我反复练这道题还有一个原因：它可以当“手速基准线”。闭眼写、不出错、五分钟之内完成，说明归并的基础肌肉记忆已经建立，可以进入下一关了。

3.2 215 数组中的第 K 个最大元素：归并能做，但你要知道更优解

有读者可能会问：“第 K 大这种题，我用堆一行就完了，为什么要提归并？”问得没错。215 这道题的常规解法是快速选择或者堆，时间复杂度分别为平均 O(n) 和 O(n log k)，都比归并的 O(n log n) 好。

那我把这道题放进路线里的价值是什么？价值在于让你建立“方案取舍”的意识。面试时你给出归并排序解法，可能不会被直接判错，但面试官下一句大概率是“你能优化到 O(n) 吗？”如果你对快速选择和堆都了如指掌，那归并版本就当练手；如果你只背了归并一种排序，那就成了暴露知识盲区的时刻。

所以 215 的正确刷法，是至少掌握“归并能过 + 快选最优”两层理解。归并版本写出来，证明你手里有排序工具；快选写出来，证明你知道在什么场景换工具。

3.3 从基础题里挖出的隐藏考点：稳定性与递归深度

912 和 215 做完之后，如果你只是“把题过了”，那收获其实很小。基础题真正值钱的是隐藏考点。

第一个是稳定性。力扣不会直接问“归并排序稳定吗”，但它会通过逆序对题考察你：相等元素到底算不算逆序对？这就逼你必须理解<=的语义。

第二个是递归深度。对一个长度为 10^5 的数组归并，递归树深度约 17 层；对 10^9 的数据，约 30 层。分治的深度增长是 log 级别的，这决定了归并可以处理大规模数据。反过来，如果某个“归并变式题”你把递归深度写成了 O(n)，那基本就是错了，面试官很容易顺着这个点追问。

第三个是空间。基础模板每层递归都新建tmp，实际上空间复杂度会退化到 O(n log n)。虽然 912 题用 Python 提交也能过，但到了 327 区间和这种大数据量题目，频繁分配临时数组会明显变慢。所以进阶做法是准备一个全局临时数组，所有递归层共享一份。后面我讲逆序对时会用这个写法，读者可以对比感受差异。

4. 归并排序的杀手锏：逆序对与“右侧小于当前元素”的统一套路

4.1 从暴力 O(n^2) 开始：逆序对到底在数什么

先看剑指 Offer 51：给定数组，求一共有多少对(i, j)满足i < j且nums[i] > nums[j]。比如[3, 1, 2]，逆序对有(3,1)、(3,2)，一共 2 个。

暴力解法非常直观，两个 for 循环就行：

def reversePairs_brute(nums): n = len(nums) cnt = 0 for i in range(n): for j in range(i + 1, n): if nums[i] > nums[j]: cnt += 1 return cnt

但数组长度到 10^5，O(n^2) 就别想过了。题目不会让你暴力数每一对，它考验的是你能不能把“成对比较”这件事压缩到合并阶段里一次算完。

4.2 归并排序如何“顺手”统计逆序对

核心思路一句话：在合并两个有序区间时，如果右边区间取出了一个元素nums[j]，而左边区间还有元素nums[i]没有取出，那么说明nums[i]到nums[mid]的所有元素都比nums[j]大。这些元素都在nums[j]的左侧，于是它们和nums[j]全部构成逆序对，数量就是mid - i + 1。

这就是“一次合并统计一批”，而不是“一对一看”。看代码：

def merge_sort_count(nums, left, right): if left >= right: return 0 mid = left + (right - left) // 2 cnt = merge_sort_count(nums, left, mid) cnt += merge_sort_count(nums, mid + 1, right) tmp = [] i, j = left, mid + 1 while i <= mid and j <= right: if nums[i] <= nums[j]: tmp.append(nums[i]) i += 1 else: cnt += mid - i + 1 tmp.append(nums[j]) j += 1 while i <= mid: tmp.append(nums[i]) i += 1 while j <= right: tmp.append(nums[j]) j += 1 nums[left:right + 1] = tmp return cnt

唯一的变化就在else分支里多了一行：cnt += mid - i + 1。这一行是整个逆序对问题的钥匙。

为什么相等时取左边元素，不计数？因为题目要求“严格大于”才算逆序对，nums[i] == nums[j]时不满足条件；同时我们用<=保证相等元素不被打乱顺序。如果你把<=改成<，相等元素也会被计成逆序对，答案直接错掉。

两个收尾的 while 循环里没有加计数，因为当某个区间先耗尽时，剩下的过程不再产生新的“右侧较小元素”被取出的情况，计数已经全部发生过了。

4.3 315 题计算右侧小于当前元素的个数：带着索引去归并

顺子题来了。315 要求返回一个数组answer，其中answer[i]是nums[i]右侧比它小的元素个数。难度比求总数高，因为你需要知道“每个位置上”的数量，而不只是一个总和。

麻烦在于归并排序会把元素挪来挪去，排序结束后你根本不知道该数记在谁头上。解决办法是排序时带上原始索引，让索引跟着元素一起动。

def countSmaller(nums): n = len(nums) idx = list(range(n)) ans = [0] * n tmp = [0] * n def merge(left, right): if left >= right: return mid = (left + right) // 2 merge(left, mid) merge(mid + 1, right) i, j, k = left, mid + 1, left while i <= mid and j <= right: if nums[idx[i]] <= nums[idx[j]]: ans[idx[i]] += j - (mid + 1) tmp[k] = idx[i] i += 1 else: tmp[k] = idx[j] j += 1 k += 1 while i <= mid: ans[idx[i]] += j - (mid + 1) tmp[k] = idx[i] i += 1 k += 1 while j <= right: tmp[k] = idx[j] j += 1 k += 1 idx[left:right + 1] = tmp[left:right + 1] merge(0, n - 1) return ans

你需要仔细理解的只有一件事：j - (mid + 1)是什么？它是右半区间已经被取走的元素个数。后取走的元素当然比后取走的更加靠左一些……等一下，准确说：当左半区间的idx[i]被写入结果时，右半区间已经被取走了多少个元素？这些元素都位于原始数组的右侧，且值都比当前左元素小，所以它们就是“右侧小于当前元素”的个数。

这句话值得反复读三遍。我第一次接触这个写法时也绕了很久，最简单的验证方法就是拿一个短数组像[5, 2, 6, 1]手动模拟一遍。你会发现每个位置统计的数字完全正确，整个算法的神奇之处就在这行代码里。

4.4 同型变体：翻转对、区间和、小和问题

掌握了 315，等于掌握了一整族题目的核心套路。它们的共同点是：排序的目的不再只是让数组有序，而是让合并阶段能为“跨左右区间”的统计提供便利。

到了这一步，归并排序就不再是“排序算法”了，它是一个分治统计框架。做题的时候先问自己一个问题：这个题能不能拆成左右两半？合并时能不能借助“两边都有序”的条件一次性算出一个批量答案？如果能，归并就大概率是一条可走的路。

5. 链表版归并：148 题排序链表为什么值得单独练一遍

5.1 为什么链表版不能直接套数组模板

数组归并靠下标访问元素，链表可不行。你拿不到mid位置的下标，只能用指针走一遍才能找到中间节点。而且合并时如果还用临时数组，那就失去意义了——链表版的价值就在于用指针“穿针引线”，把额外空间压到 O(1)，只靠递归栈的 O(log n)。

148 排序链表题目要求时间复杂度 O(n log n)、空间复杂度 O(1)，这正好是归并排序链表版的用武之地。它练两个核心基本功：切分链表、合并链表。

5.2 快慢指针找中点与切断链表

找中点用快慢指针是链表题的基本功：慢指针每次走一步，快指针每次走两步，快指针到尾时，慢指针就是中点。

def sortList(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 = sortList(head) right = sortList(mid) ...

这里有个特别容易踩的坑：fast的初始值必须是head.next而不是head。如果fast也从头开始走，偶数长度的链表切分后两半会不均匀，更麻烦的是递归时可能永远切不断，导致死循环。让快指针先进一步，慢指针最终落在“偏左”的位置，这样slow.next之后的部分就是右半段，切断后两边互不纠缠。

切断链表用slow.next = None这一行，很多人会忘。忘了会怎样？左右两个子链表还连着，递归排序时你根本不知道边界在哪，排序结果乱七八糟。所以每次切完，检查一下“左半段末尾的 next 是不是空”，这是链表调试时我最先看的地方。

5.3 合并两个有序链表的 dummy 节点写法

数组版合并用临时数组，链表版合并用 dummy 节点，本质上都是“开一个新容器装结果”。

def mergeTwoLists(l1, l2): dummy = ListNode(0) p = dummy while l1 and l2: if l1.val <= l2.val: p.next = l1 l1 = l1.next else: p.next = l2 l2 = l2.next p = p.next p.next = l1 if l1 else l2 return dummy.next

dummy节点的作用是让你不需要单独判断“结果链表的头到底是谁”。无论 l1 还是 l2 先被选中，dummy.next都能统一返回。最后接上剩余部分，链表合并完成。

把 5.1 到 5.3 连起来，148 的完整解法就是：递归切分、排序左右、合并返回。原本数组版里“辅助数组”的概念彻底消失了，整个过程只剩下指针的重新连接，空间也做到了常数级。这道题做完，你对“归并是一种结构操作”的理解会比只刷数组版深得多。

6. 调试归并排序时我踩过的坑：临时数组、边界条件与中间态

6.1 我写崩过的几种代码

代码写得再熟，也没人能保证一次跑通。下面这几类错误是我自己实际遇到并排查过很久的，列出来供你自查。

第一类：临时数组的作用域问题。有人会在每一层递归里都tmp = []再从头填充。小数组没事，大数组会又慢又占内存。更隐蔽的是，如果tmp被定义成递归函数里的局部变量，但你又想在另一处引用它，程序就会诡异。我的建议是基础阶段随便，进入逆序对阶段后统一用共享临时数组。

第二类：写回数组时区间边界写错。nums[left:right+1] = tmp很容易手滑写成nums[left:right] = tmp。这一下就漏掉了最后一个元素。排查方法很简单，排序完打印一段，看看是否所有元素都在，以及是否有序。

第三类：逆序对计数在收尾循环里漏加。315 这种题，两个清理 while 循环里都要有ans[idx[i]] += j - (mid + 1)。为什么？因为左区间还没取完时，右区间可能已经被取走了一部分，那些元素仍然算“已经出现的右侧较小元素”。漏了任何一个清理循环，结果都会少算。用短数组对拍，这种错误立刻现形。

6.2 小数据集手推递归树：最笨但最有效的调试

写归并按脑子里逻辑推不出来的，建议用手推。拿一个长度 4 的数组，比如[4, 3, 2, 1]，把递归树完整画一遍，看每一层递归的left、mid、right是多少，合并后数组变成什么。

为什么长度 4？因为长度 4 的递归树刚好三层，覆盖了分到不能再分的完整过程；再长一点就容易乱了。手推完之后你会突然明白哪些变量在递归过程中是如何变化的，之后再写 315 这种带索引数组的版本，至少不会被递归绕晕。

这个笨办法的价值在调试链表版时更明显：数组还能打印，链表断掉你无处下手。老老实实画一遍head和mid的切分过程，很多死循环问题一眼就能定位。

6.3 打印中间态的实用技巧：在合并入口打日志

调试归并排序一个比较好用的办法，是在合并函数入口打印一行关键信息：

print(f"merge: left={left}, mid={mid}, right={right}") print(f"before: {nums[left:right+1]}") # 合并结束后再打印一次 print(f"after: {nums[left:right+1]}")

这样你会看到整个数组从乱序到有序的步进过程。哪个区间没有合并、哪个区间合并结果不对，一眼就能看出来。面试题调试时间紧，我不会用复杂断点，打印大法反而最快。写完代码还要小测：随机生成长度 100 的数组，跑一个暴力解法跟归并解法对拍，结果一致才敢提交。

6.4 性能优化视角：原地归并值得做吗

关于“原地归并排序”，网上有不少讨论。理论上可以做到 O(1) 额外空间，但实现极其复杂，旋转交换会引入大量常数开销，实际性能往往还不如普通归并。对刷题和面试来说，我建议不要在这上面浪费时间。

真正值得优化的反而是“减少临时数组分配次数”这一件事。用共享的tmp数组替代每层新建列表，在大数据量的题里能明显提升速度。而且它让代码结构更接近生产环境的手法——很多排序场景下，减少分配和回收就是最实在的优化。

如果你已经能写出稳定的归并、能轻松改出逆序对版本、能在链表上完成切分合并，那归并这个知识点就已经不是你的瓶颈了。剩下的，就是在遇到新题时多想一步，它能不能拆成两半？合并时能不能顺路数点东西？想通这两问，你已经远远超过“会写模板”的层次。

我个人这几年刷题下来最大的体会是：归并排序像一棵树的骨干，看着普通，但很多分支题都从它长出来。树状数组、线段树能做的高频统计题，归并往往也能做，而且思路更朴素、调试更直接。下一次再刷力扣，看到“右侧小于当前元素”“翻转对”“区间和”这类题，别急着绕路，先试试归并这把旧工具，它很少让你失望。