，还顺手帮你数清逆序对？)
昨天我们被快排的随机化和三路切分折腾得够呛，今天换个“老实人”——归并排序。
它没有快排的花哨，但胜在稳定：最好、最坏、平均都是O(nlogn)，且天生稳定，不需要任何随机化技巧。
更妙的是，在归并的过程中，你可以顺手数出数组中的逆序对数量——这本来是Hard级别的题（剑指 Offer51），但归并排序只需加一行代码就能搞定，复杂度依然是 O(nlogn)。
今天我们就用归并排序搞定LC.912，再顺势拿下逆序对计数，一箭双雕。
📦 题目速览（30 秒读懂）
题目1：排序数组（LC.912）
给你一个整数数组
nums，将其升序排列。
示例：[5,2,3,1]→[1,2,3,5]
题目2：逆序对计数（剑指 Offer51 / LCR170）
如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。求数组中逆序对的总数。
示例：[7,5,6,4]→ 输出5（解释：(7,5),(7,6),(7,4),(5,4),(6,4)）
约束：长度 ≤ 5×10⁴，暴力O(n²)必挂。
🧠 核心思路：分治的另一种姿势——先拆后合，逆序对藏在合并里
暴力慢在哪？
- 排序：选择/插入O(n²) → 超时。
- 逆序对：双重循环枚举所有
i<j，比较nums[i] > nums[j]→ O(n²)，且逆序对数量本身可达O(n²)（倒序数组），但我们需要的是计数而不是枚举。
归并排序的“分治”哲学
- 分：把数组从中间一分为二，递归排序左右两半，直到每半只剩一个元素（天然有序）。
- 合：把两个有序数组合并成一个更大的有序数组——用双指针分别扫描，每次取较小者放入临时数组。
为什么快？合并两个总长为n的有序数组只需O(n)，递归树高度O(logn)，总O(nlogn)。
逆序对怎么“免费”数出来？
当合并左右两半时，左右内部都已经有序。此时如果右半的当前元素right[j]小于左半的当前元素left[i]，那么由于左半有序，从left[i]到左半末尾的所有元素都大于right[j]，并且它们原始位置都在right[j]之前。所以可以一口气数出mid - i + 1个逆序对（i是当前左指针的位置）。
这就是“批发”计数，而不是一个一个枚举，从而把O(n²) 优化到O(nlogn)。
关键：归并排序本身就是有序合并的过程，逆序对计数只是多累加一行，完全免费。
🖼️ 图解算法（逆序对计数过程）
以nums = [7,5,6,4]为例，递归拆分：
[7,5,6,4] ├─ [7,5] ──┬─ [7] │ └─ [5] └─ [6,4] ──┬─ [6] └─ [4]自底向上合并，关注逆序对产生：
| 合并 | 左半（有序） | 右半（有序） | 触发逆序对的情况 | 计数累加 |
|---|---|---|---|---|
| [7] 与 [5] | [7] | [5] | 5<7，左半剩余 [7] 都与5成对 | +1 |
| [6] 与 [4] | [6] | [4] | 4<6，左半剩余 [6] 都与4成对 | +1 |
| [5,7] 与 [4,6] | [5,7] | [4,6] | 4<5，左半 [5,7] 都与4成对 → +2；6>5取5不计；6<7，左半 [7] 与6成对 → +1 | +3 |
总计数 = 1+1+3 =5，正确 ✅
可见，每次“右半元素被取走而左半还有剩余”时，批量计入逆序对。
💻 代码实现（Python + Java，二合一）
Python 版（归并排序 + 逆序对可选）
classSolution:defsortArray(self,nums:List[int])->List[int]:self.merge_sort(nums,0,len(nums)-1)returnnumsdefmerge_sort(self,nums,lo,hi):iflo>=hi:returnmid=(lo+hi)//2self.merge_sort(nums,lo,mid)self.merge_sort(nums,mid+1,hi)self.merge(nums,lo,mid,hi)defmerge(self,nums,lo,mid,hi):tmp=nums[lo:hi+1]# 复制到临时数组i,j=0,mid-lo+1# i左半起点，j右半起点（相对于tmp）forkinrange(lo,hi+1):ifi>mid-lo:# 左半用完nums[k]=tmp[j];j+=1elifj>hi-lo:# 右半用完nums[k]=tmp[i];i+=1eliftmp[i]<=tmp[j]:# 相等取左 → 保持稳定nums[k]=tmp[i];i+=1else:# 若需数逆序对，在这里加：# count += (mid - lo) - i + 1nums[k]=tmp[j];j+=1Java 版（专门用于逆序对计数，LCR 170）
classSolution{privateintcount=0;publicintreversePairs(int[]record){if(record.length<2)return0;mergeSort(record,0,record.length-1);returncount;}privatevoidmergeSort(int[]nums,intlo,inthi){if(lo>=hi)return;intmid=lo+(hi-lo)/2;mergeSort(nums,lo,mid);mergeSort(nums,mid+1,hi);merge(nums,lo,mid,hi);}privatevoidmerge(int[]nums,intlo,intmid,inthi){int[]tmp=newint[hi-lo+1];System.arraycopy(nums,lo,tmp,0,hi-lo+1);inti=0,j=mid-lo+1;for(intk=lo;k<=hi;k++){if(i>mid-lo){nums[k]=tmp[j++];}elseif(j>hi-lo){nums[k]=tmp[i++];}elseif(tmp[i]<=tmp[j]){// 相等取左，稳定nums[k]=tmp[i++];}else{// 关键：右半较小，左半剩余全部 > tmp[j]count+=(mid-lo)-i+1;nums[k]=tmp[j++];}}}}⚠️关键点：
- 稳定性来自
tmp[i] <= tmp[j]时取左半，相等时左半原位置在前，顺序保留。- 逆序对计数只需在
else分支加一行count += (mid - lo) - i + 1，其余不变。- 临时数组
tmp是必需的，因为合并时原数组会被覆盖，无法同时读取左右段。
⏱️ 复杂度分析（面试必问）
- 时间：每层合并O(n)，共logn 层 →O(nlogn)，不依赖数据分布，稳定可靠。
- 空间：临时数组O(n) + 递归栈 O(logn) →O(n)。这是稳定性和确定性性能的代价。
🚀 举一反三：4 道高频变种题，一套框架通吃
| 题目 | 变化点 | 应对策略 |
|---|---|---|
| LC.493 翻转对 | 统计nums[i] > 2*nums[j]的数量 | 归并框架，但在 merge之前用双指针单独统计（因为 2 倍关系与归并顺序不完全同步） |
| LC.327 区间和的个数 | 统计满足条件的子数组和个数 | 前缀和 + 归并计数，同一套路 |
| LC.148 排序链表 | 对链表排序 | 归并排序是链表排序的首选（快排在链表上partition别扭） |
| LC.剑指 Offer 51 | 纯逆序对计数 | 直接套上面的Java版即可 |
💬 面试追问模拟（提前准备，惊艳全场）
Q1：归并排序为什么稳定？
因为合并时，当左右元素相等，我们优先取左半（使用
<=判断）。这样左半中相等的元素会先被放入结果，它们原始顺序保持不变，整体稳定性得以维持。
Q2：归并排序和快排，你选哪个？
- 归并：稳定、最坏 O(n log n)、需要 O(n) 额外空间 → 适合对象排序、外部排序、需要稳定性的场景。
- 快排：不稳定、最坏 O(n²)（随机化后概率低）、原地排序、缓存友好 → 适合基本类型排序、内存敏感场景。
Java 的Arrays.sort()对基本类型用快排变体，对对象用 TimSort（归并 + 插入）。
Q3：外部排序是怎么用归并思想的？
数据太大装不进内存：分批读入内存，排好序写成有序的“归并段”（run），然后对这些段进行多路归并（用小顶堆或败者树）合并成一个大文件。多路归并可以减少磁盘 I/O 次数，是数据库和 MapReduce 的基础。
Q4：逆序对计数能不能用快排？
不能。快排不涉及两个有序子数组的合并过程，无法批量获得跨区间的逆序信息。归并排序天然适合这种“跨左右统计”的问题。
🧩 实战小技巧（刷题党必备）
- 口诀：拆到底，合有序；相等取左稳；跨区间，批量数。
- 模板：凡是需要“统计跨左右区间的某种关系”且区间内有序可复用，优先考虑归并排序。
- 防坑：临时数组一定要复制完整区间；索引计算别搞错（特别是 mid 的偏移）。
📈 实际应用场景（不止是刷题）
- Java 对象排序：
Arrays.sort(Object[])使用 TimSort（归并 + 插入排序优化）。 - 数据库外部排序：处理大文件排序时的归并阶段。
- 稳定多关键字排序：先按部门排，再按工资排，稳定保持部门内顺序。
- Git 合并：合并有序提交历史树时也用归并思想。
🎁 今日思考题
如果题目要求统计“非严格逆序对”（即
nums[i] >= nums[j]就算），代码需要改哪里？
提示：只需将tmp[i] <= tmp[j]改成<，这样相等时会取右半，左半剩余与右半相等元素都计入。
你能写出这个改动吗？
