企业官网建设流程全解析

归并排序，我在刚开始刷力扣的时候，觉得它就是个标准排序算法，背完模板就放到一边了。后来真正在 hard 题里遇到“统计右侧比当前元素小的个数”“翻转对”“区间和的个数”，才反应过来，归并排序不只是排序，它是一整套能在合并阶段顺便统计和变形的高效框架。这篇文章就把我刷 LeetCode 归并排序相关题目时总结的模板、变形和坑一次性说清楚。如果你现在觉得归并排序只会用在一道排序数组题上，那这篇应该能帮你打开思路。

1. 归并排序的核心思想与通用模板

1.1 分治里面最容易被忽视的“合并有序”

归并排序的核心动作其实不是拆分，而是合并。拆分只是把数组分成两半，真正干活的是 merge 函数：它接收两个已经有序的子数组，用双指针把它们合并成一个整体有序的数组。这个过程有点像你手里有两叠已经按大小排好的扑克牌，每次只需要比较最上面那张，把小的拿走继续比，直到其中一叠空了，再把另一叠剩下的全补上。因为两个子数组有序，所以合并的代价是线性的，不会出现嵌套比较的情况。

分治策略选择对半分，每一层所有子问题的总规模加起来还是 n，递归深度是 log n，最终总体复杂度是 n log n。这里有一个很多刷题新手会踩的认知偏差：他们觉得归并排序主要的时间消耗在递归上，实际上递归只是逻辑上的分割，没有额外比较，所有比较都发生在 merge 阶段，而且每一层只有 O(n) 次比较。理解这一点之后，再去想“在合并阶段顺便统计一些东西”就会觉得非常自然，因为 merge 过程本身就是一对一遍历比较，信息量最大的地方就在这里。

1.2 递归模板和自底向上的迭代写法

直接给出一个我常用的模板，区间用的是左闭右开 [l, r)，这样可以避免 mid 取整带来的边界困惑。以 C++ 为例：

void mergeSort(vector<int>& nums, int l, int r, vector<int>& temp) { if (r - l <= 1) return; int mid = (l + r) / 2; mergeSort(nums, l, mid, temp); mergeSort(nums, mid, r, temp); // 合并 int i = l, j = mid, k = l; while (i < mid && j < r) { if (nums[i] <= nums[j]) temp[k++] = nums[i++]; else temp[k++] = nums[j++]; } while (i < mid) temp[k++] = nums[i++]; while (j < r) temp[k++] = nums[j++]; for (int p = l; p < r; ++p) nums[p] = temp[p]; }

注意我用了<=，这样能保证归并排序的稳定性。如果你在统计逆序对时想保证相等元素的相对位置不变，这个细节就很重要。还要注意 temp 数组是在函数外面创建的，不要在 merge 里 new，否则反复分配内存会很伤性能。

迭代写法用自底向上的归并，每次合并长度为 len 的相邻区间，len 从 1 翻倍到大于 n。这种写法虽然不依赖递归，但实现起来比递归更容易错，核心是控制边界：

void mergeSortIterative(vector<int>& nums) { int n = nums.size(); vector<int> temp(n); for (int len = 1; len < n; len *= 2) { for (int left = 0; left < n; left += 2 * len) { int mid = min(left + len, n); int right = min(left + 2 * len, n); // 合并 [left, mid) 和 [mid, right) int i = left, j = mid, k = left; 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 = left; p < right; ++p) nums[p] = temp[p]; } } }

迭代的好处是可以看到归并排序的层次，对理解分治也是很大的帮助。面试时我一般先讲递归，因为逻辑更直观，如果需要优化空间或避免递归栈，再补充迭代方案。

1.3 时间复杂度和空间复杂度到底怎么算的

很多人直接背结论 O(n log n) 和 O(n)，但没有理解为什么。时间复杂度可以用递推式 T(n) = 2T(n/2) + O(n) 来表示，意思是把 n 规模的排序拆成两个 n/2 的排序，最后用线性时间合并。展开这个递推式，会发现每一层的所有合并加起来都是 O(n)，一共有 log n 层，所以总时间 O(n log n)。

空间复杂度则是辅助数组 temp 占了 O(n)，递归栈的深度 O(log n)，但通常把问题规模外部的辅助数组作为主导。这里有个“就地排序”的念想，归并排序理论上可以通过一些技巧做原地归并，但会牺牲时间效率，得不偿失，所以我在实际刷题中从不追求原地归并。遇到需要空间复杂度更低的场景，优先考虑其他排序算法，但碰到跟归并排序的“合并时统计”强相关的题目，空间换时间是值得的。

2. 力扣典型题拆解：从排序题到链表题

2.1 912题：排序数组，练模板的最佳入口

LeetCode 第 912 题就是给你一个整数数组，让你排序。这是最直白的归并排序应用场景。实操时注意几点：边界条件，如果数组长度是 5，传入的是 [0,5)，分到 [0,2) 和 [2,5)，再继续分下去，不会出现无限递归。模板中的 mid = (l + r) / 2，由于区间是左闭右开，mid 永远落在左区间，不会出现普通闭区间那样 l=0,r=1,mid=0 时左右区间仍然分成 [0,0] 和 [1,0] 的尴尬情况。

我用这个模板解决 912 题时，并没有直接调用系统排序，而是自己实现了归并，一方面为了锻炼，另一方面是想验证后续变形题的模板是否干净。912 题相当于一个基准测试，如果你的模板能完全正确运行，再往下做变形题就顺很多。我还会专门用几个边界用例去跑：空数组、只有一个元素、两个元素、完全升序、完全降序、存在大量重复值。这六个用例跑完，模板基本就是稳的。

2.2 148题：排序链表，归并排序的链表改版

链表没法用数组式随机访问，快排在这会退化，堆排序也没法直接做，所以递归归并排序反而是最佳选择。基本思路是：用快慢指针找到链表中间节点，将链表从中间断开成两段，分别递归排序，然后合并两个有序链表。

快慢指针的写法需要注意初始化和边界，常见错误是 fast 和 slow 都从头开始，然后 fast 每次走两步，slow 走一步，当 fast 到达末尾时，slow 就是中点。具体我这样写：

ListNode* sortList(ListNode* head) { if (!head || !head->next) return head; ListNode *slow = head, *fast = head->next; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } ListNode* mid = slow->next; slow->next = nullptr; ListNode* left = sortList(head); ListNode* right = sortList(mid); return mergeTwoLists(left, right); }

注意 fast 初始化为 head->next，是为了让最终 slow 停在左半段的最后一个节点而不是偏右。如果不这么做，对于两个节点的链表 [1,2]，slow 会停在 2，slow->next 是 nullptr，导致左半段变成 [1,2]，右半段变成空，直接死循环。这个坑是链表归并里最经典的边界错误。合并两个有序链表时就简单，创建一个虚拟头节点，按序拼接即可。

整个排序链表的空间复杂度主要来自递归栈，是 O(log n)，满足 148 题要求的 O(n log n) 时间就够了。如果你想做到严谨的 O(1) 空间，可以用迭代自底向上归并链表，但我个人觉得面试先讲递归版更清晰，迭代版作为加分项。链表归并的核心价值在于：你学会了在没有随机访问的数据结构上依然保持稳定的 n log n 排序，这是很多其他排序做不到的。

2.3 23题：合并K个升序链表，归并的扩展思维

这道题虽然可以直接用优先队列做，但归并排序的思路也很重要。它可以理解为对 k 个链表做归并排序的“合并”部分：两两合并，形成 log k 层，每层处理整个链表集合的总节点数为 N，所以时间复杂度 O(N log k)，而且不需要额外的堆空间，只是递归栈 O(log k)。

写分治合并的代码时，依然可以复用 mergeTwoLists：

ListNode* mergeKLists(vector<ListNode*>& lists, int l, int r) { if (l > r) return nullptr; if (l == r) return lists[l]; int mid = (l + r) / 2; ListNode* left = mergeKLists(lists, l, mid); ListNode* right = mergeKLists(lists, mid + 1, r); return mergeTwoLists(left, right); }

这里面每个子问题返回的是一个升序链表，合并过程跟归并排序里的 merge 完全相同。相较于顺序合并，分治合并的优势非常明显，顺序合并复杂度 O(Nk)，因为第一个链表会被合并 k 次，分治则让每个节点只参与 log k 次合并。所以以后遇到“合并 K 个有序序列”，优先考虑分治，这也是归并排序思想在复杂问题里的真实威力。

3. 归并排序的进阶应用：统计类问题

3.1 逆序对：合并时顺手统计的经典套路

逆序对的定义是 i<j 且 a[i] > a[j]，统计一个数组中有多少对这样的组合。暴力法是 O(n^2)，但用归并排序可以在合并阶段统计，做到 O(n log n)。原理是这样的：当左半部分和右半部分都已经有序后，我们在合并时用 i 指向左半部分，j 指向右半部分。如果 a[i] <= a[j]，正常取左边；如果 a[i] > a[j]，这说明右半部分的 a[j] 小于左半部分从 i 开始的所有元素。因为左半部分从 i 到 mid 的元素都大于等于 a[i]（实际上是有序的，大于 a[i]），也就都大于 a[j]。于是对于当前 a[j]，左半部分里至少有 mid - i + 1 个元素可以跟它组成逆序对，把这个数量累加到计数器即可。这个 “mid - i + 1” 就是逆序对统计的核心公式。

注意，如果区间采用左闭右开，那么对应的是 mid - i。具体看模板而定。我在面试中遇到这道题时，有一个容易忽略的细节：结果可能会超出 int 范围，例如一个降序排列的 100000 长度数组，逆序对数量是约 50 亿，所以计数器要用 long long。这道题往往是很多复杂统计题的基础，比如后面的 315 题，本质就是逆序对思想的“定向记账”。

3.2 315题：计算右侧小于当前元素的个数

这道题要求返回一个数组，对于每个位置 i，统计右侧有多少个元素小于 nums[i]。如果我们只统计总数，那就和逆序对一样，但现在要把计数“分配”到每个具体元素上。思路是在归并时同时维护元素的原始下标。实际操作时，我们不再直接对元素排序，而是维护一个数组 indices，里面存的是原始下标，排序时比较的是 nums[indices[i]] 和 nums[indices[j]]。

合并时，当从左半部分取出一个下标 i（表示原数组第 i 个元素），此时右半部分已经取了多少个元素，这取出的每个元素都小于当前左元素，于是 res[i] 要加上这个数量。反过来，当从右半部分取出元素时，说明右元素更小，右侧已经取出的数量加一。相等的情况要优先取左半边，保证“严格小于”被正确统计。我把这个过程写成代码：

void merge315(vector<int>& nums, int l, int r, vector<int>& indices, vector<int>& res, vector<int>& temp) { if (r - l <= 1) return; int mid = (l + r) / 2; merge315(nums, l, mid, indices, res, temp); merge315(nums, mid, r, indices, res, temp); int i = l, j = mid, k = l, rightTaken = 0; while (i < mid && j < r) { if (nums[indices[i]] <= nums[indices[j]]) { res[indices[i]] += rightTaken; temp[k++] = indices[i++]; } else { rightTaken++; temp[k++] = indices[j++]; } } while (i < mid) { res[indices[i]] += rightTaken; temp[k++] = indices[i++]; } while (j < r) temp[k++] = indices[j++]; for (int p = l; p < r; ++p) indices[p] = temp[p]; }

我一开始写的时候总想着把 index 和值放在 pair 里排序，后来发现用索引数组更简单。核心就是记住 “rightTaken 记录右侧已经取走多少个元素”，每取一次左侧元素，说明右侧这些取走的元素都比它小，所以直接累加到对应的结果里。这道题是逆序对思想的高级版，非常值得反复练习。

3.3 493题：翻转对

翻转对要求 nums[i] > 2 * nums[j] 且 i<j。因为存在乘 2，所以不能像逆序对那样在合并中直接比较左右指针。但我们可以利用左右两半都有序的性质，在合并之前先用双指针统计跨区间的翻转对。因为左右两半内部的对数已经在递归时统计完毕，所以合并前只需要统计左边的一个元素和右边的一个元素的组合。

统计方法是：遍历左半部分的每个元素 x，用指针 j 在右半部分找到最后一个满足 x > 2 * nums[j] 的位置，那么从右半部分起点到 j 的所有元素都满足条件，计数加上 j - mid（这里按左闭右开区间写，具体看自己的模板）。同时因为左半部分是有序的，x 是在递增的，所以 j 也只会往右移动，不会回退，整体还是线性时间。然后照常合并排序。

这里有一个坑：比较时 2 * nums[j] 可能超出 int 范围，要转成 long long 再比较，LeetCode 默认用 int 存储，虽然例子不大，但边界测试用例经常卡死你，所以别省这个转型。这道题能帮你理解“统计的范围不一定非要在 merge 的过程中完成，有时候利用有序性在 merge 前单独扫一遍”也是一种通用套路。

3.4 327题：区间和的个数

这道题是归并排序变形里比较难的一道，本质上是前缀和 + 分治统计。首先求出前缀和数组 s，其中 s[0]=0。原数组的下标 i 到 j-1 的和可以表示为 s[j] - s[i]。题目要求这个和在 [lower, upper] 内，等价于 s[i] 落在 [s[j] - upper, s[j] - lower] 这个区间里。现在我们只需要统计 i<j 且满足这个区间条件的前缀和对数量。

归并排序在这里的作用是：对前缀和数组 s 进行排序，但在合并前，先利用左右两半已经有序的性质统计跨左右的前缀和对。对于右半部分的每个值 s[j]，我们可以在左半部分中维护两个指针 left、right，分别指向第一个使得 s[i] >= s[j] - upper 的位置和第一个使得 s[i] > s[j] - lower 的位置，两者之间的元素数量就是满足条件的个数。因为左半部分有序，这两个指针只会向右移动，保持线性。统计完后再合并排序。

这里统计的是原始意义上的 i<j 吗？注意，因为左右两个半区在前缀和数组中的原始下标天然就是左半的下标都小于右半的下标，所以跨半区的任意组合都满足 i<j，这个性质是分治统计的前提。这道题涉及的前缀和数组要开 n+1 大小，并且因为数字很大，超过 32 位，要用 long long。我记得刚开始写时没加 long long，直接用 int，结果样例都过不了。这些细节看起来小，但决定了一道 hard 题能不能一次 AC。

4. 常见问题与排查技巧实录

4.1 递归边界和区间端点的选择：为什么我建议左闭右开

大部分教科书喜欢写闭区间 [l, r]，但刷题时我强烈建议统一用左闭右开。原因是左闭右开可以天然避免 mid 的歧义。例如一个区间长度为 1 时，r-l=1，递归自然停止；拆分子区间时，[l,mid) 和 [mid,r) 永远不会重叠。如果执意用闭区间，合并时 mid = (l+r)/2，子区间是 [l,mid] 和 [mid+1,r]，这样写也对，但一定要小心长度为 2 时 l=0,r=1,mid=0，左边 [0,0]，右边 [1,1]，不会死循环；但如果你把右边写成 [mid, r] 就会发生死循环。所以选择一个自己熟悉的风格，不要混用。

在写递归参数时，我还会额外注意 mid 的计算不要写成(l + r + 1) / 2，除非你用的区间定义强制要求右中位数。归并排序用左中位数就可以保证区间不断缩小，不需要担心死循环。这个看起来基础，但我在看别人代码时经常发现边界混乱导致的 bug，源头就是左右区间定义没想清楚。

4.2 临时数组的复用与赋值时机

很多初学者每次 merge 时新建一个 vector，虽然结果对，但效率差，而且面试中会被追问优化。正确做法是在入口函数中创建一次 temp，传递引用给所有递归调用。合并时先把结果写入 temp，最后再拷贝回原容器。有一个提升性能的习惯：如果左半部分的最后一个数已经小于等于右半部分的第一个数，说明整体已经有序，可以直接跳过合并避免无谓的拷贝。这个优化在已经有序的数组上非常有效，很多排序库也这么干。

另外，当你写的是统计类题目时，拷贝回原数组的这段代码不能漏。很多人把统计逻辑加进 merge 后，只记得更新计数，忘记把 temp 里的内容写回原数组，导致下一次递归的左右部分其实并没有真的有序。这样的后果是统计结果时而对时而不对，非常隐蔽。调试的时候如果发现计数飘忽，先检查这一步。

4.3 逆序对统计中的数据类型坑

逆序对数量最大可以达到 n(n-1)/2，当 n=100000 时，这个数字是 4,999,950,000，远超 int 的 2147483647，所以直接用 int 存会溢出。315 题的结果数组用 int 没问题，因为每个元素右侧的元素个数最多 n，但如果你把计数器用来汇总，还是要小心。493 题涉及到乘法溢出，327 题涉及前缀和溢出，统一用 long long 是王道。这里说的 long long 特指 64 位整数，在 LeetCode 里足够应对常见规模。

如果是其他语言，比如 Python 就没有这个顾虑，但在 C++/Java 里这是高频出错的点。我建议在写统计变量之前先估算一下最坏规模，不要等溢出造成答案错误再去怀疑算法。

4.4 递归深度和对栈空间的理解

归并排序的递归深度是 log n，对于 n=10^5 的数组，深度也就 17 层，不会导致栈溢出。这个深度和快速排序的最坏情况完全不同，所以归并排序在递归安全上更稳。但链表的递归版同样深度 log n，也不会有问题。不过有些面试官会追问能不能用迭代归并实现 O(1) 空间，这个时候如果你能写出自底向上的迭代链表归并，会非常加分。我在日常刷题中会先把递归版写熟练，再抽时间练迭代版，不是为了炫技，而是为了在细节层面真正理解归并的层次。

5. 刷题路径与调试心得

5.1 建议的刷题顺序与练习方法

我自己的刷题路径是：先把 912 题的递归模板默写三遍，再把 148 链表的边界折腾清楚，然后去刷逆序对相关题目。每刷一道 hard 题，我都会回到那个 merge 函数里重新看一遍，因为统计逻辑其实都是 merge 的“副产物”。千万不要试图死记硬背解法，而是理解“有序子数组合并的过程中，左右两部分的相对顺序能给我们带来什么信息”。

具体顺序可以这样安排：先 912，再做一道逆序对统计（可以用题号不确定但大家都叫剑指 Offer 51 的那道），然后做 315，再做 493，最后挑战 327。这样从模板到统计计数，再到索引数组和前缀和，难度是阶梯上升的。每一步迭代，都把 merge 函数的核心逻辑在纸上画一遍，尤其是“右指针取元素时左指针剩余的数量”到底意味着什么，画多了就不容易忘。

5.2 一个很实用的调试技巧：先合并后加统计

做这类归并排序变形题，强烈建议在 merge 函数里先只做合并，不加统计逻辑，跑通后再把统计逻辑加进去。因为统计逻辑容易把合并的索引搞乱，分步验证可以让你在出错时快速定位到底是合并写错了，还是统计公式不对。我踩过好几次“合并没问题但统计偏大”的坑，最后发现都是因为我把相等元素错误地也算进去了，导致非严格小于被统计。

举个具体例子：315 题里，如果你在合并比较时用的是<而不是<=，那么相等元素也会被算作“右侧小于当前元素”，结果会偏大。这个错误很难肉眼发现，因为只在包含重复元素的用例里暴雷。所以我会故意用一组包含大量重复元素的输入去测，一旦结果不对，优先检查所有比较符号是不是严格。这个方法帮我省了大量调试时间。归并排序的变形题看着唬人，但只要严格执行“先纯排序、再加统计、最后做边界测试”，其实成功率很高。