归并排序求逆序对：从分治思想到高效代码实现

1. 题面与第一直觉：暴力解法为什么撑不过大数据

很多人第一次接触归并排序时，都把它当成一个普通排序算法来学：分两半，分别排好，再合并。这个理解当然没错，但总觉得少了点味道。直到遇到逆序对个数这道题，我才真正感受到归并排序的精华不在"排序"本身，而在"分治过程中能顺手统计出很多信息"。

逆序对的定义非常简单：给定一个数组，如果存在下标i < j且a[i] > a[j]，那么(a[i], a[j])就算一个逆序对。换句话说，就是前面某个数比后面某个数大，位置和大小关系相反了。比如数组[3, 1, 2]中，(3,1)和(3,2)是逆序对，(1,2)不是，总共 2 个。初学者最容易想到的做法是两层循环枚举所有i < j，逐个比较，复杂度显然是 O(n^2)。当n只有几千时问题不大，可一旦n到了十万、百万级别，这种写法就会直接超时，不仅在线判题系统会卡住，真实业务场景里处理大规模序列时也完全不可用。

暴力解法的瓶颈在于它浪费了大量重复比较。举个例子，[5,4,3,2,1]这个完全逆序的数组，逆序对总数是5 * 4 / 2 = 10，而两层循环确实会比较所有 10 对组合。问题是，如果数组已经分成前后两段，且两段内部各自有序，那么统计两段之间的逆序对时，完全没必要一个接一个地比，可以通过批量的方式一次算出很多对。这个"批量"的思维，正是归并排序解法能降到 O(n log n) 的关键。

还有一个值得留意的直觉：逆序对的数量，等于把一个数组通过相邻交换变成有序数组所需的最少交换次数。冒泡排序每交换一次相邻逆序元素，恰好消掉一个逆序对，所以它的交换次数就等于逆序对个数。这个等价关系说明逆序对不仅是"数大小关系"，它天然对应着一种操作代价，在求"最小交换次数"或"排序代价"的题目里经常冒出来。

2. 归并排序分治框架里的计数玄机

2.1 计数时机：不是"归并后"再数，而是"归并时"就数

归并排序的核心是分治：把数组从中间分成左右两半，递归排序，然后合并两个有序子数组。如果把"统计逆序对"和"归并排序"结合起来，最直接的想法是先递归统计左右两半内部的逆序对，再做一次全数组范围的统计。但这个全数组范围的统计如果又用两层循环，复杂度还是 O(n^2)，等于白干。

真正的做法是把计数嵌入merge过程：当合并两个有序子数组时，凡是发现"右边某个数小于左边当前指向的数"，那么左边从当前指针到左半末尾的所有数，都和这个右边数构成逆序对。因为左右两半都已经各自有序，左边剩余的数必然都大于右边当前这个数，于是可以一口气加上一大片计数，不用逐个比较。

这个过程极其自然，但要理解它为什么是对的，需要盯住一个前提：合并操作发生之前，左右两半内部已经分别排好序。正因为有序，才能用"长度"来批量计数。如果不排序，这个批量计算就没有依据，这也是为什么必须在归并过程中统计，而不能把排序和统计分成互不相干的两步。

2.2 核心公式：为什么是mid - i + 1

很多人第一次看到归并排序求逆序对的代码时，会对那一行count += mid - i + 1感到困惑：明明只是两个数在比较，怎么突然加上一堆？

假设当前合并left..mid和mid+1..right这两段，指针i指向左段正在比较的位置，指针j指向右段正在比较的位置。如果发现a[i] > a[j]，说明左段里从i到mid的所有元素都大于a[j]。为什么？因为左段已经有序，a[i..mid]是递增的，既然最小的a[i]都比a[j]大，后面的自然更大。而右段里j之前的位置已经在前面处理过了，不会和a[j]再组成新的逆序对。所以此时能确定的逆序对数量就是mid - i + 1。

这里最容易犯的错误是写成count++，以为当前两个数正好是一对。可惜这样会漏掉大量本可以批量统计的逆序对。比如左段是[5,7,9]，右段是[4,6,8]，当5和4比较时，不仅(5,4)是逆序对，(7,4)、(9,4)同样也是。如果只加 1，后面每个右段元素到来时又在左段当前指针处单独比较，逻辑上也不是完全错，但会多出很多次无谓的扫描，复杂度退化回 O(n^2)。

用公式来印证一下：归并排序在处理完全逆序的数组[n, n-1, ..., 1]时，第一次合并两个单元素，会产生 1 对；第二次合并两个长度为 2 的有序段，左段元素全部大于右段，累计增加 1+2+1+2...，最终总计数一定是n(n-1)/2。如果代码里的批量计数写对，任何一个测试都能对上这个公式，这是验证实现是否正确的最快方法。

2.3 取左还是取右：一个<=就能决定稳定性

合并过程中还有一个细节值得单独提：当a[i] <= a[j]时，我们会把左边的a[i]放进临时数组，指针i后移；只有当a[i] > a[j]时，才把右边的a[j]放进临时数组并增加计数。这个<=不是随意写的，它保证了两个关键属性。

第一，稳定性。归并排序是稳定排序，等值元素的相对顺序不会被打乱。如果用<判断，那么当a[i] == a[j]时会先取右边，两个相等元素的相对顺序就反了，排序不再稳定。对纯排序算法来说，不稳定在某些场景下可能无所谓，但逆序对的定义里"相等不算逆序对"，所以等值时绝不能触发计数。

第二，避免重复计数。如果等值时走了count += mid - i + 1的分支，会把相等的元素也算成逆序对，结果偏大。我在帮人 review 代码时见过不止一次这种 bug：看起来只是少写了一个等于号，实际结果在含重复数据的用例上差了一大截。

3. 完整代码实现与一次手工走查

3.1 Java 实现：把细节一次写对

我用 Java 写一个最常用的版本。这里故意把临时数组的创建放在递归入口之外，避免每次merge都重新new int[]，性能会好很多。

public class InversionCounter { public long countInversions(int[] nums) { if (nums == null || nums.length < 2) { return 0; } int[] temp = new int[nums.length]; return mergeSortAndCount(nums, temp, 0, nums.length - 1); } private long mergeSortAndCount(int[] arr, int[] temp, int left, int right) { if (left >= right) { return 0; } int mid = left + (right - left) / 2; long count = 0; count += mergeSortAndCount(arr, temp, left, mid); count += mergeSortAndCount(arr, temp, mid + 1, right); count += mergeAndCount(arr, temp, left, mid, right); return count; } private long mergeAndCount(int[] arr, int[] temp, int left, int mid, int right) { for (int i = left; i <= right; i++) { temp[i] = arr[i]; } int i = left; int j = mid + 1; int k = left; long count = 0; while (i <= mid && j <= right) { if (temp[i] <= temp[j]) { arr[k++] = temp[i++]; } else { count += (mid - i + 1); arr[k++] = temp[j++]; } } while (i <= mid) { arr[k++] = temp[i++]; } while (j <= right) { arr[k++] = temp[j++]; } return count; } }

这里我把temp复制了left..right这一段，也可以只在合并时创建长度为right - left + 1的临时数组，然后拷贝回原数组对应位置。两种写法都常见，前者一次性申请最大空间、稍微省一点反复分配的开销，后者更贴近很多教材的写法。两种我都实测过，数据量到了百万级，前者会明显更稳。

还有一个细节：mid = left + (right - left) / 2而不是(left + right) / 2，主要为了防止left + right溢出。在普通题目里left + right不太会超过int范围，但养成习惯总是好的。

3.2 一个具体例子的逐步推演

拿[7, 5, 3, 4]来走一遍，验证代码逻辑。

第一层递归：left=0, right=3, mid=1。左边排序[7,5]：mid=0，合并时7 > 5，左段剩余元素 1 个，所以count += 1，数组变为[5,7,3,4]。右边排序[3,4]：3 <= 4，直接合并，count += 0，数组变为[5,7,3,4]。

第二层合并：现在左段是[5,7]，右段是[3,4]。比较5和3，5 > 3，此时左段从i=0到mid=1共 2 个元素，所以count += 2，把3放入结果。比较5和4，5 > 4，又是 2 个元素，count += 2，把4放入结果。最后左段剩余两个，直接拼接。最终count = 1 + 2 + 2 = 5。

手动枚举验证：[7,5,3,4]中，7和后面三个数都是逆序对，共 3 个；5和3、5和4是逆序对，共 2 个；3和4不是。合计 5 个，完全一致。走查的时候会发现，第二次合并时两次count += 2非常高效，一个循环就把原先需要四次比较的统计做完了。

3.3 计数变量为什么必须用 long

逆序对个数最多可能是多少？完全逆序时是n(n-1)/2。当n = 100000时，这个值是4,999,950,000，已经超过int的2,147,483,647。所以计数变量必须用long或语言对应的 64 位整数类型。很多人在小数据上跑通后，一上大数据就出现负数或者溢出导致的错误结果，问题往往就出在这里。

如果题目要求取模，那么每一处累加都可以先取模，但要注意取模后的中间值不能用来参与大小比较逻辑——顺手比较的是原数组元素，不是累加的计数。我把这两种场景分开建议：明确说答案可能很大的，用long；明确要求对某个模数取模的，在count +=时立刻取模，返回时再取一次。别为了省那几行代码用int，等到溢出再排查会非常痛苦。

4. 复杂度、边界与稳定性：教科书没说透的部分

4.1 时间复杂度递推式：为什么总能稳定在 O(n log n)

归并排序求逆序对的时间复杂度可以用递推式表达：T(n) = 2 * T(n/2) + O(n)。意思是处理规模为n的问题，需要分别处理两个规模n/2的子问题，再加上一次线性时间的合并。根据主定理，这个递推式的解是O(n log n)。

比这个式子更重要的是理解它为什么不会退化。其他很多分治算法可能因为切分不均匀而退化到 O(n^2)，但归并排序每次都是严格从中间切分，递归深度固定为log n，每一层的总合并时间加起来是 O(n)，所以总复杂度永远是 O(n log n)，最坏、平均、最好都是这个量级。对求逆序对来说，这意味着输入数据的排列方式不会影响运行时间上界，这在算法竞赛和面试中是一个很大的优点。

我记得有人会问：递归调用本身不也有开销吗？确实有，但每层的递归调用次数是 2 的幂次增长，单次开销很小，log n层总共也就 O(n) 次调用，和合并的线性开销同阶，不会主导复杂度。实际项目里如果数据量特别大，可以把递归深度大约估一下，n到一亿时深度不过 27 层，完全不用为栈空间担心。

4.2 空间复杂度：O(n) 的临时数组到底怎么省

归并排序的经典实现需要额外 O(n) 空间，这也是它对比原地排序算法（如堆排序）的短板。求逆序对时，我们同样需要一块临时数组，所以空间复杂度也是 O(n)。

很多教材讲归并排序时会提到"原地归并"的优化，但我要提醒一句：实现原地归并通常非常复杂，而且常数因子巨大，实际性能往往还不如用额外空间的版本。我在某个项目里试过用"旋转法"做原地归并来省空间，结果代码难度翻了几倍，运行速度还变慢了。除非内存被卡到必须 O(1) 空间，否则直接用临时数组是更理性的选择。

如果你担心递归调用栈的额外空间，它也是 O(log n)，和 O(n) 的临时数组相比可以忽略。整体空间复杂度记作 O(n) 是准确的。

4.3 边界情况：空数组、单元素、全相等、全逆序

我把实际测试中最常见的几类边界情况整理成一个表，方便自测时逐项对照。

全相等数组特别值得注意。如果用<而不是<=判断，这个用例会返回 6，而不是 0。我在面试模拟中问过不少人，他们能写出归并的框架，却在这个等号上翻车。

4.4 稳定性在逆序对问题里的隐藏价值

归并排序是稳定排序，这一性质在求逆序对时不只是一个"额外优点"，它和计数逻辑是互相绑定的。

设想一个场景：数组里有两个相等的元素，一个在左段，一个在右段。它俩之间不应该构成逆序对。归并排序因为遇到相等时优先取左边，所以不会出现"右边相等元素提前跑到前面去"的情况，也就自然避免了对这两个元素的重复计数。如果换成不稳定排序，你很难保证相等的左右元素不会在合并时交错，进而导致统计规则混乱。

所以，把这个<=看作一个排序性质之外的正确性要求，而不是可有可无的细节。它和公式mid - i + 1一样，是这道题实现里不可或缺的一环。

5. 一题多解：树状数组、离散化与归并排序怎么选

5.1 树状数组离散化的思路

除了归并排序，逆序对还有一种非常常见的解法：把原数组的值离散化，然后逐个遍历，用树状数组维护"已经出现过的数"的个数。每次遇到一个新数a[i]，先查询树状数组里小于当前值的数量，再用当前已经扫描过的总个数减去它，得到的就是以这个数为"逆序对右端"的逆序对数量。

为什么要离散化？因为树状数组的下标必须是整数且不能太大。如果原始数据是10^9量级的整数，不可能直接开一个这么大的数组。离散化的标准做法是：把原数组拷贝一份排序，然后用二分查找把每个元素映射成"它是第几小的数"。排序后相同的值映射到同一个排名，查询时能严格排除相等元素，保证逆序对定义中的"严格大于"条件。

// 伪代码：离散化 + 树状数组 int[] sorted = nums.clone(); Arrays.sort(sorted); int[] rank = new int[nums.length]; for (int i = 0; i < nums.length; i++) { rank[i] = Arrays.binarySearch(sorted, nums[i]) + 1; } long ans = 0; BIT bit = new BIT(nums.length); for (int i = 0; i < nums.length; i++) { int lessOrEqual = bit.query(rank[i]); ans += i - lessOrEqual; bit.update(rank[i], 1); }

这段思路的时间复杂度同样是 O(n log n)，其中排序和二分都是 O(n log n)，树状数组每次query和update是 O(log n)。它和归并排序的时间复杂度是同阶的，但常数通常更小，代码也更短。

5.2 两种做法的适用场景对比

归并排序解法和树状数组解法各有千秋。归并排序不需要额外离散化，对数据值域没有要求，哪怕是浮点数、字符串这类能比较大小但不方便做下标的元素，它都能直接处理。树状数组则需要把元素对应成整数排名，离散化时要求元素可排序，而且通常只适合数字类数据。

还有一个重要区别：归并排序是稳定的，它的计算过程不会改变"相等元素不计数"的规则；树状数组离散化时同样能保证相等元素排名一致，但如果你不小心把 query 写成"小于等于"再减，就会漏掉相等元素的处理。两者各有坑，没有绝对优劣。

从代码量看，如果面试要求 20 分钟内写出可运行代码，归并排序版更稳，因为它不需要额外的数据结构类定义。如果面试官追问"能不能换一种方法优化常数"，树状数组就是很好的进阶回答。在算法竞赛中，很多选手偏爱树状数组，因为它可以很方便地支持动态修改和查询，和归并排序的静态快照式统计不是一个思维模型。

5.3 从逆序对延伸开的问题

逆序对不只存在于数组排序题里。有一个经典应用是衡量两个序列的一致性：把两个序列中的一个映射成"每个元素在另一个序列里的排名"，排名序列的逆序对个数就代表两个序列的差异程度。这在统计学里对应一种叫做秩相关的概念，在推荐系统的离线评估中也能见到类似思想。

在算法题中，由逆序对延伸出的变体非常多。比如"翻转对"要求满足i < j且a[i] > 2 * a[j]，这就不能简单地在合并时用a[i] > a[j]直接批量计数，得在合并前单独扫描一遍数组做条件判断。再比如二维平面上统计"每个点右下方有多少个点"，可以按某个维度排序后用树状数组处理。这些问题本质上都还在用同一套思想：借助有序性，把原本 O(n^2) 的枚举降成 O(n log n)。

正因为这套思想能复用，我才建议把归并排序求逆序对当成一个"母题"来学。把mid - i + 1那个公式彻底想明白，后面遇到类似的分治统计题，推导新公式时会顺手很多。

6. 实测踩坑记录与自测数据清单

6.1 我踩过的高频坑

第一个坑是递归函数里count写成了局部变量，每次递归返回时没有累加，导致最后结果只有最底层合并那一次产生的计数。这种错误经常被编译器静默放过，因为代码能跑，样例也不一定每次都挂。排查方法很简单：打印每个mergeAndCount的返回值，手动加起来对一遍。

第二个坑是合并前把临时数组复制错了范围。我写过一个版本，在mergeAndCount里只复制left..mid，然后另一个循环复制mid+1..right时下标写成了arr[start++]，结果原数组在合并过程中被自己覆盖，排序结果错得一塌糊涂。后来我改成先统一拷贝整个[left,right]到临时数组，再逐位写回原数组，思路清晰很多。

第三个坑和大量测试用例有关：一个全局计数器在多个测试用例之间没有清零。某些在线判题系统会把多个测试数据放在同一份代码的一次进程里运行，如果计数器是静态成员变量，必须在主函数入口重新置零。这种问题往往只有在完整测试集跑完才会暴露，单测小样例根本发现不了。

第四个坑是性能层面的：count += mid - i + 1虽然本身是 O(1) 操作，但如果临时数组每次合并都新建，内存分配和 GC 开销会非常大。我之前用一百万元素做压力测试，每次新建临时数组的版本耗时大约是不复用版本的 3 倍。数据量上了千万，这个差距会进一步拉大。

6.2 自测数据与期望输出

我建议把下面这组数据直接拿去做单元测试。前几个都是手工就能验证的边界，最后一个随机大数组可以配合暴力算法对拍。

最后一个[2,2,1,1]可以手算验证：第一个 2 和两个 1 构成 2 对，第二个 2 又和两个 1 构成 2 对，总共 4 对；两个 2 之间不算，两个 1 之间也不算。如果代码输出 6，说明相等元素被误计了。

6.3 对拍技巧与性能体会

写配套的暴力解法来对拍，是非常好的排错手段。生成一个长度几万的小数组，分别跑暴力 O(n^2) 和归并解法，逐项比对结果。两者一旦不一致，把数组缩小，二分定位到第一个出错的位置，调试效率会高很多。

我自己的习惯是写一个随机数生成器，测试长度从 2 开始一直翻倍到几十万，每次跑完都对一下结果。归并排序求逆序对的实现一旦过了这个对拍流程，后面搬到各种题目里基本不会因为逻辑错误翻车。

最后讲一个我实际用下来的性能体会：在普通个人电脑上，用 Java 跑一百万元素的完全逆序数组，归并解法大概需要几百毫秒级别，暴力解法直接跑不动。换到一亿元素时，归并解法需要的内存大约是几百兆字节，已经接近常规题目的极限。如果你的应用场景里数组规模很大，但元素取值范围很窄，可以优先考虑树状数组加离散化，内存占用会稍微小一些。如果元素不是整数，归并排序就是更稳妥的选择。

写这道题最值得记住的一句话是：归并排序不只是"排好序"，它天然提供了一种有序结构，让计数不再需要逐个比较。理解了mid - i + 1为什么成立，很多看似复杂的分治统计问题都会变得清晰起来。