企业官网建设流程全解析

归并排序：面试被问懵之后，我把 LeetCode 上所有相关题一次啃透了

先交代一下背景。去年集中刷 LeetCode 的时候，我一度很排斥归并排序——总觉得直接调sort()不就完了，手写这玩意儿干嘛？直到某次模拟面试被问到“如何统计数组中的逆序对”，我脑子里闪过一堆思路，最后连一个能跑的归并代码都没写利索。面试官没说什么，但那个微笑我记到现在。

后来我把归并排序在 LeetCode 上的经典题全部梳理了一遍，从模板到变体、从递归到迭代、从排序到计数，摸透了之后才发现：归并排序根本不只是一个“排序算法”，它是一套极其通用的分治框架。排序只是它的表面能力，利用合并过程的顺序信息去解决计数、统计、区间类问题，才是它真正的价值所在。这篇文章把我踩过的坑、总结出的模板、以及几种高频题目的完整解法全部整理出来，希望对正在刷题的你有用。

1. 归并排序在面试题里的真实地位

1.1 面试官到底在考什么

先说一个判断：如果你面试时只被要求“手写归并排序”，那多半是热身题。真正的考点从来不是你能不能写出归并那两行合并逻辑，而是以下几个方面：

• 是否理解分治的递归展开过程，能否徒手画出递归树；
• 是否知道归并排序是稳定排序，且稳定性的来源在哪里；
• 能否从“合并两个有序数组”的过程里，联想到逆序对、区间和统计等衍生问题；
• 是否能在递归和迭代两种实现之间自由切换，并说清各自的优劣势。

换句话说，归并排序是面试官探测你算法基本功的探针。你只背模板，就只答对了第一问；真正理解了归并过程的结构化特征，后面几个问题才能稳。

1.2 归并排序和快速排序的边界感

很多初学者会把归并排序和快速排序搞混，因为两者都是“分治”。但又有一个关键区别：快速排序是“先分组再处理”，分组的过程本身就带着 partition 的排序动作，属于原址排序；归并排序则是“先拆到底再合并”，真正做事的是合并阶段，而且需要额外空间。

这个区别直接决定了你会遇到什么问题：

• 快排难在 partition 的边界处理和退化情况（比如有序数组）；
• 归并难在内存开销、递归栈深度、以及合并时指针越界。

如果你用归并排序刷题，空间复杂度 O(n) 一般是可接受的，但你要是拿它去处理一个上亿的数据集，就得考虑外部排序的思路了。后面我会专门讲这个扩展方向。

2. 归并排序核心原理：分治框架与复杂度推导

2.1 分治三步走

归并排序的框架在任何语言里都是同一套逻辑，可以抽象成三步：

1. 分解（Divide）：把数组从中间切成两半，得到左子数组和右子数组；
2. 解决（Conquer）：递归地对两个子数组分别排序；
3. 合并（Combine）：把两个已经有序的子数组合并成一个大的有序数组。

整个过程终止条件是：子数组长度为 0 或 1，此时天然有序，直接返回。听起来非常简单，但真正写代码的时候，绝大部分 bug 都出在第 3 步的合并边界上，后面我会专门列出来。

2.2 时间复杂度推导为什么是 O(n log n)

时间复杂度是数学推导出来的，值得自己手推一遍，而不是死记结论。假设问题规模为 n，每一步把数组分成两半，所以递归树的深度是 log₂n 层；每一层上，所有合并操作加起来都要扫描 n 个元素。所以总复杂度是每层的工作量 n 乘以层数 log n，即 O(n log n)。

这里有两个容易忽略的点：

• 归并排序的时间复杂度与输入数据是否有序无关。即使数组已经全部有序，它依然要逐层拆分、逐层合并，所以最好、最坏、平均都是 O(n log n)。这一点是它和快速排序最大的差异：快排有序退化到 O(n²)，归并不会。
• 如果你在递归里每次都用slice之类的语法复制子数组，你会多出 O(n log n) 的复制开销。刷 LeetCode 时数据量一上来就容易 TLE 或超内存。正确做法是：只开一个临时数组，全程复用，通过索引范围描述子数组，不做数组物理切割。

2.3 稳定性来源与空间复杂度

稳定性指的是：值相同的元素，排序后相对位置不变。归并排序是稳定排序，稳定性从哪来的？就在合并时那个<=的等号上。当前半段元素等于后半段元素时，我们优先取前半段，这样相等的元素保持了原来的相对次序。

所以提醒一句：如果你在合并代码里把<=误写成<，稳定性就被破坏了。在纯排序场景可能看不大出来，但在“按多个字段排序”或“保持原始序号”等问题里，这个细节直接决定答案对不对。

空间复杂度方面，归并排序需要一个长度为 n 的临时数组，所以空间复杂度是 O(n)。递归调用本身还要占用栈空间，深度 O(log n)，但 O(n) 的临时数组是大头。LeetCode 上归并排序相关题目的内存限制一般都能过，但如果你同时复制了多个数组，就会翻车。

3. 两种实现模板：递归写法与迭代写法

3.1 递归模板（以 Java 为例）

LeetCode 刷题最常用的还是递归写法，逻辑清晰，面试时也好讲。下面这段是我反复精简后的模板：

class Solution { public int[] sortArray(int[] nums) { mergeSort(nums, 0, nums.length - 1, new int[nums.length]); return nums; } private void mergeSort(int[] nums, int left, int right, int[] temp) { if (left >= right) return; int mid = left + (right - left) / 2; mergeSort(nums, left, mid, temp); mergeSort(nums, mid + 1, right, temp); merge(nums, left, mid, right, temp); } private void merge(int[] nums, int left, int mid, int right, int[] temp) { int i = left; int j = mid + 1; int k = 0; while (i <= mid && j <= right) { if (nums[i] <= nums[j]) { temp[k++] = nums[i++]; } else { temp[k++] = nums[j++]; } } while (i <= mid) { temp[k++] = nums[i++]; } while (j <= right) { temp[k++] = nums[j++]; } for (int p = 0; p < k; p++) { nums[left + p] = temp[p]; } } }

几个关键点：

• left + (right - left) / 2而不是(left + right) / 2，是为了防止 left + right 溢出。这种细节在面试中会加分，但归根结底是防 bug 的实用习惯。
• temp数组在sortArray里一次性创建，传递给递归过程复用，避免每层递归都 new 数组。
• 合并结束后回填原数组时，要从left + p的位置开始写，不是从 0 开始写。初次手写归并的人经常在这里犯错，导致每次合并后前半段数据错乱。

3.2 迭代模板：自底向上的归并

递归版本虽然直观，但面试官有时会追问：“你能不能写非递归版本？”因为递归有栈深度风险，某些场景下（比如处理超长数组）迭代版本更稳。

自底向上的思路是：先把数组看成 n 个长度为 1 的有序段，然后每相邻两个段合并一次，得到长度为 2 的有序段；接着两两合并得到长度为 4 的有序段……不断翻倍，直到整个数组合并完成。

class Solution { public int[] sortArray(int[] nums) { int n = nums.length; int[] temp = new int[n]; for (int len = 1; len < n; len *= 2) { for (int left = 0; left < n - len; left += 2 * len) { int mid = left + len - 1; int right = Math.min(left + 2 * len - 1, n - 1); merge(nums, left, mid, right, temp); } } return nums; } private void merge(int[] nums, int left, int mid, int right, int[] temp) { int i = left; int j = mid + 1; int k = 0; while (i <= mid && j <= right) { if (nums[i] <= nums[j]) { temp[k++] = nums[i++]; } else { temp[k++] = nums[j++]; } } while (i <= mid) { temp[k++] = nums[i++]; } while (j <= right) { temp[k++] = nums[j++]; } for (int p = 0; p < k; p++) { nums[left + p] = temp[p]; } } }

注意迭代版本的几个边界：

• 外层循环len表示当前有序段长度，每次翻倍。
• 内层循环left从 0 开始，步长为2 * len，每次处理两个相邻长度为len的段。
• mid = left + len - 1不能漏掉- 1，否则区间会多出一个元素。
• 最后一个段的right可能超过数组末尾，必须用Math.min(..., n - 1)截断，否则越界。

迭代版本的空间复杂度同样是 O(n)，但它避免了递归栈，适合在嵌入式或资源受限环境里排序。LeetCode 刷题时，用递归版本就足够，不过迭代写法能体现你的理解深度。

3.3 两种写法的对比与选择

4. LeetCode 实战场景拆解

4.1 排序数组（第 912 题）

这是归并排序最直接的 LeetCode 场景。题面很简单：给你一个整数数组，要求升序排序。很多人第一反应是用Arrays.sort()，但如果你刷这道题的目的是练排序算法，直接调 API 就白费了。

我的建议是：用这道题作为归并排序模板的验证场。把上面的递归模板贴进去，直接提交，能过就说明你的基础实现没问题。注意题目的取值范围比较大，如果代码里出现 O(n²) 的意外复杂度就会超时，而归并排序的 O(n log n) 是稳定可过的。

4.2 数组中的逆序对（剑指 Offer 第 51 题）

这道题是归并排序最常见的面试变体，也是我认为最值得深挖的一道题。题面是：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求逆序对总数。

最暴力的解法是两层循环，O(n²)。但当 n 达到 50000 甚至更大，暴力必挂。归并排序解法是基于一个核心观察：合并两个有序数组时，如果右半段的当前元素小于左半段的当前元素，那么左半段从当前元素到结尾的所有元素，都和右半段的这个元素构成逆序对。

道理不复杂：因为左半段内部是有序的，当前元素是左半段剩余部分的最小值。如果这个最小值都大于右半段当前的元素，那么左半段剩余的所有元素都大于它，所以一次性可以累加mid - i + 1个逆序对。这就是归并过程里“多算一步统计”的思想。

参考代码如下：

class Solution { private long count = 0; public int reversePairs(int[] nums) { mergeSort(nums, 0, nums.length - 1, new int[nums.length]); return (int) count; } private void mergeSort(int[] nums, int left, int right, int[] temp) { if (left >= right) return; int mid = left + (right - left) / 2; mergeSort(nums, left, mid, temp); mergeSort(nums, mid + 1, right, temp); merge(nums, left, mid, right, temp); } private void merge(int[] nums, int left, int mid, int right, int[] temp) { int i = left; int j = mid + 1; int k = 0; while (i <= mid && j <= right) { if (nums[i] <= nums[j]) { temp[k++] = nums[i++]; } else { count += mid - i + 1; temp[k++] = nums[j++]; } } while (i <= mid) { temp[k++] = nums[i++]; } while (j <= right) { temp[k++] = nums[j++]; } for (int p = 0; p < k; p++) { nums[left + p] = temp[p]; } } }

为什么count用long？因为逆序对数量最坏情况是数组完全逆序，比如[n, n-1, ..., 1]，逆序对总数是 n*(n-1)/2，n 稍微大一点就会超出 int 范围。LeetCode 题目本身不要求取模，所以要用long存结果，最后转回int。

这道题的价值在于：它展示了归并排序的合并过程不仅是“排序”，而是在“比较两个有序序列”的时候可以顺手完成某种统计。这种思想可以迁移到很多“区间统计”类问题。

4.3 排序链表（第 148 题）

链表上的归并排序是另一个高频考点。普通数组排序可以直接按下标切分，链表不行，需要利用快慢指针找到中点，然后递归排序前后两段，最后合并两个有序链表。

链表归并与数组归并最大的不同是：不需要额外 O(n) 空间（严格来说不需要临时数组），只需要调整指针。所以链表归并排序的空间复杂度是 O(log n)，来自递归栈。

核心代码如下：

class Solution { public ListNode sortList(ListNode head) { if (head == null || head.next == null) return head; ListNode slow = head; ListNode fast = head.next; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } ListNode rightHead = slow.next; slow.next = null; ListNode left = sortList(head); ListNode right = sortList(rightHead); return mergeTwoLists(left, right); } private ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(0); ListNode cur = dummy; while (l1 != null && l2 != null) { if (l1.val <= l2.val) { cur.next = l1; l1 = l1.next; } else { cur.next = l2; l2 = l2.next; } cur = cur.next; } if (l1 != null) cur.next = l1; if (l2 != null) cur.next = l2; return dummy.next; } }

链表归并要注意两个细节：

• 找中点时，fast初始化为head.next，这样当链表长度为 2 时，slow会落在第一个节点上，保证左右两段都非空。如果fast = head，长度为 2 时slow会落在第二个节点，left为空，递归就永远无法结束。
• slow.next = null这一步不能省，它负责切断左右两段，否则递归排序右半段时，还是能够通过next指针访问到左半段的节点。

链表归并排序的时间复杂度也是 O(n log n)，虽然快慢指针找中点每次要扫描 O(n/2)，但整体递归树的每层总工作量仍然是 O(n)，所以总复杂度不变。

4.4 区间和计数类问题（第 327 题）

归并排序还有一种更隐蔽的应用：区间和统计。以第 327 题“区间和的个数”为例，题面是给定数组，要求计算区间和在 [lower, upper] 范围内的个数。

暴力做法是枚举所有区间，O(n²)，超时。用归并排序怎么优化？核心思路是：

1. 计算前缀和数组prefixSum，区间[i, j]的和就是prefixSum[j] - prefixSum[i - 1]；
2. 问题转化为：在前缀和数组中有多少对(i, j)满足lower <= prefixSum[j] - prefixSum[i] <= upper；
3. 归并排序在合并左右两个有序前缀和子数组时，可以顺带统计满足条件的数对数量。

这一步统计的核心是：由于左右两个子数组都是有序的，对于每个左段元素，右段中满足区间条件的元素会落在一个连续的范围内，可以用两个指针l和r维护这个范围的边界。具体逻辑比较精巧，不是简单的“逆序对 +1”能概括的，建议先搞懂逆序对版本，再来看这题。

这类问题的意义在于：它揭示了归并排序的合并阶段可以承载“两个有序序列之间的配对计数”这一通用操作。逆序对是基础版，区间和计数是进阶版。一旦你理解了这层抽象，遇到其他“有序配对统计”的问题，都可以尝试用归并框架去套。

5. 常见问题与排查技巧

5.1 越界与死循环问题

归并排序里最常见的崩溃就是数组越界。出现越界时，优先检查这几个位置：

• mid = left + (right - left) / 2是否正确；
• 递归终止条件left >= right是否写成了left > right；
• 迭代版本中right是否用Math.min截断；
• 合并回填时是否从left偏移开始写。

死循环则多半是因为边界计算错误导致子区间没有缩小，常见于链表找中点时fast初始化不对，或者递归时切分区间重叠。

5.2 合并阶段的三个经典坑

第一个坑前面已经解释过。第二个坑我刚才也提到了，这里再强调一次：合并完后，temp数组里有序元素是从 0 开始的，但目标位置不是从 0 开始，必须从left开始回填。第三个坑很容易理解但特别容易漏，当一边数组耗尽时，另一边一定还有剩余元素，要把它们全部拷贝过去，否则结果就缺元素。

5.3 调试归并的实操方法论

我实测下来最有效的调试手段是：用小型随机数组加断言。具体操作是写一个测试函数，对随机生成的数组分别用Arrays.sort()和你的归并排序跑一遍，然后比对结果。这样能快速暴露合并和回填的问题。

如果结果不对，再加一个“打印递归过程”开关。在merge方法开头打印left、mid、right和当前数组内容，肉眼追踪一遍合并过程，基本就能定位是切分错了还是合并错了。

注意：调试时不要直接拿 LeetCode 的大数据用例硬跑，那样输出太多反而看不清问题。数据量固定在 8 到 16 个元素，加上随机打乱，打印出每一步的状态，很快就能发现问题。

6. 归并排序的扩展与现实应用

归并排序在编程面试之外，还有很多现实应用场景，理解这些能帮你在面试里回答“为什么学这个”的问题，也能让你对算法有更整体的认识。

最经典的是外部排序。想象一个场景：内存只有 2GB，但磁盘上有一个 20GB 的文件需要排序。你不可能一次性把所有数据加载进内存，这时就用到了归并排序的分治思想。先把大文件切分成若干个小块，每块都能加载进内存排序，排序后写回磁盘；然后再多路归并这些有序块，最终生成一个完整的有序文件。归并排序支持“分段处理、逐步合并”的特性，让它成为外部排序的地基。

另一个场景是数据库的多路归并。数据库执行排序操作时，如果排序数据超过内存缓冲，就会使用类似外部排序的方案。归并排序的稳定性和可控性，使它成为数据库内部实现排序算子的重要工具。

还有 MapReduce 框架中的 Shuffle 阶段：Map 端的输出需要按键排序后再传递给 Reduce 端。这个排序过程在数据量巨大时也是通过归并排序的分段合并思想来实现的。很多分布式计算引擎里，实际上都是先在每个分区内排序，再对所有分区做多路归并。

这些场景本质上都是同一个模式：数据太大放不进内存，或者数据分布在多个节点，无法一次性全局排序，那就先局部有序，再逐层合并。归并排序“只需要比较两个有序序列”的局部特性，让它在这种场景下几乎是唯一的选择。

所以，即使你在 LeetCode 上不会遇到“20GB 文件排序”这种题，理解归并排序的合并机制，对你理解底层系统的设计也很有帮助。面试官如果问到“归并排序还有哪些应用”，你能说出外部排序和数据库多路归并，往往会成为加分项。

7. 一些实战心得

最后分享几个刷题过程中总结出来的经验，算是给读者的额外福利。

第一，模板要固化，但不要死背。归并排序的模板并不长，关键在于每次写的时候，心里要清楚每一步在做什么，而不是照抄。我建议你至少手写五遍，每一遍都慢下来，把递归树画一遍，把合并过程用笔记模拟一遍。等你闭上眼睛能完整默写出递归和迭代两个版本，再去做变体题就顺了。

第二，变体题的突破口在于“合并时能做什么计算”。归并排序的框架里，merge阶段比较两段有序数组的过程，天然暴露了元素之间的相对顺序关系。逆序对、区间和计数，都是利用合并时的顺序信息避免重复扫描。遇到这类问题，先问自己：能不能通过归并的合并阶段来统计答案？如果可以，大概率就是归并的变体。

第三，注意与其它排序的搭配使用。在排序链表这题中，归并排序看起来就是个自然的答案，因为链表的随机访问成本高，不适合快排，而堆排序又需要额外结构。实际面试中，如果问题限定空间复杂度 O(1)，你就要想想链表归并是否能用迭代 + 指针技巧把递归栈也省掉，这又是一个进阶话题。

说实话，归并排序的代码量不大，但涉及的思想密度很高。从朴素的排序，到逆序对统计，再到区间和计数，再到外部排序，一条线走下来，你会发现自己对分治的理解上了一个台阶。刷题不是目的，能在一道题里看到一类问题、一个框架、一套可迁移的方法论，才算真正有所收获。