如何用归并排序在 O(n log n) 时间内求数组的逆序对数量？

简化版

逆序对指下标 i<j 但 a[i]>a[j] 的数对。暴力枚举是 O(n²)。用归并排序：在合并两个有序半的时候顺带统计——当右半的 a[j] 比左半当前的 a[i] 还小，说明左半从 i 到 mid 的所有元素都比 a[j] 大，一次性加上 mid−i+1 个逆序对。借归并的 O(n log n) 框架，总复杂度就是 O(n log n)。核心是「左右已各自有序，一次比较就能数出一批逆序对」。

详细版

逆序对分三类：左半内部的、右半内部的、跨左右两半的。归并的两次递归分别负责数「左半内部」和「右半内部」，合并这一步负责数「跨半」的——三部分不重不漏，加起来就是总数。

int reversePairs(int[] a) {
    return mergeCount(a, 0, a.length - 1, new int[a.length]);
}
int mergeCount(int[] a, int lo, int hi, int[] tmp) {
    if (lo >= hi) return 0;
    int mid = lo + (hi - lo) / 2;
    // 左半内部 + 右半内部
    int count = mergeCount(a, lo, mid, tmp) + mergeCount(a, mid + 1, hi, tmp);
    // 合并，顺带数「跨半」逆序对
    int i = lo, j = mid + 1, k = lo;
    while (i <= mid && j <= hi) {
        if (a[i] <= a[j]) {
            tmp[k++] = a[i++];        // 左 <= 右，不构成逆序对
        } else {                       // a[i] > a[j]
            count += mid - i + 1;      // a[i..mid] 都 > a[j]，各成一个逆序对
            tmp[k++] = a[j++];
        }
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= hi)  tmp[k++] = a[j++];
    for (int x = lo; x <= hi; x++) a[x] = tmp[x];
    return count;
}

a[i] <= a[j] 取左边、不计数；a[i] > a[j] 时，因为左半有序，a[i] 后面到 mid 的全都 > a[j]，一次加 mid−i+1。
排序和计数同时进行，复杂度和归并一致：时间 O(n log n)、空间 O(n)。

完整版教学

一、逆序对是什么，暴力怎么做

逆序对：数组里一对下标 (i, j)，满足 i < j 且 a[i] > a[j]——也就是「本该小的排在了大的后面」。逆序对的数量衡量一个数组的「无序程度」（有序数组 0 对，完全逆序数组 n(n−1)/2 对）。

暴力做法是双重循环枚举所有 i<j，判断 a[i]>a[j]，O(n²)。数据一大就超时，需要更快的办法——归并排序能在排序的同时把逆序对数出来，做到 O(n log n)。

二、为什么归并能顺带数逆序对

关键洞察：把逆序对按「两个元素分别落在哪一半」来分类。 对于从中点切成的左半、右半，任意一个逆序对必属于以下三类之一：

两个元素都在左半内部；
两个元素都在右半内部；
一个在左半、一个在右半（跨半）。

归并排序天然是递归结构：mergeCount(左半) 和 mergeCount(右半) 会递归地把第 1、2 类数干净（它们内部又会继续往下分）。剩下第 3 类「跨半」的，正好在合并左右两个有序半的时候数——这一步左右都已经有序，数起来特别快。三类相加，不重不漏。

三、关键：合并时一次数出一批

合并时用双指针 i（扫左半）、j（扫右半），左右都已升序排好。比较 a[i] 和 a[j]：

a[i] <= a[j]：a[i] 不比右边这个大，不构成逆序对，把 a[i] 放进结果、i++。
a[i] > a[j]：出现逆序！而且因为左半是升序的，a[i] 后面的 a[i+1], ..., a[mid] 全都 ≥ a[i] > a[j]，所以它们和 a[j] 全都构成逆序对。于是一次性加上 mid − i + 1 个，再把 a[j] 放进结果、j++。

这就是效率的来源：利用左半的有序性，一次比较数出「一整批」逆序对，而不是一个一个数。

左半 [3,5,7]（i 指向 3），右半 [2,4]（j 指向 2）
a[i]=3 > a[j]=2 → 左半从 3 到 7 共 3 个都 > 2 → count += 3

四、易错点：<= 的取舍与三类不重不漏

相等时必须用 a[i] <= a[j] 取左边、不计数。 相等不算逆序对（要求严格 a[i]>a[j]）。若写成 a[i] < a[j] 取左，会把相等也当逆序对，多算。
计数写在 else（即 a[i] > a[j]）分支里，加的是 mid − i + 1（左半从 i 到 mid 的元素个数），不是 mid − i。
别担心重复计数：递归已经把「左半内部」「右半内部」的逆序对数过了，合并只数「跨半」的，三者互不相交。
数值范围：逆序对最多 n(n−1)/2，n 大时会超过 int，计数变量要用 long（LeetCode 剑指 Offer 51 的常见坑）。

五、扩展：树状数组解法

除了归并，逆序对还能用树状数组（Binary Indexed Tree） 求：把元素离散化后从右往左（或从左往右）扫，每个元素查询「已出现的、比它小的元素个数」并累加，同时把自己加入树状数组。复杂度同样是 O(n log n)。

归并法：思路顺着分治，排序副产品，写起来直观。
树状数组法：需要离散化，但更灵活，能扩展到「区间逆序对」「二维偏序」等变体。

面试里能说清归并法就够了；提一句「也可以树状数组」是加分。

六、递归式、合并证明与数字推演

这道题的分治闭环是：左右两半内部逆序对由递归统计，合并时只统计左元素大于右元素的跨半逆序对，三类不重不漏。递归调用只保证子问题正确，原问题能否正确仍取决于合并步骤是否覆盖所有情况且不重不漏。

T(n)=2T(n/2)+Θ(n)=Θ(n log n)
递归树核对：每层子问题数 × 单个子问题的非递归代价

带数字推演：合并 [2,4] 与 [1,3]：取 1 时左侧剩 2 个元素，新增 (2,1)、(4,1) 两对；取 3 时再新增 (4,3)。推演时应记录每层输入规模、进入哪些子问题、合并新增了什么信息，不能只写最终答案。

记忆钩子：先写“分成什么、递归返回什么、怎样合并”，再列递推式；只会套主定理而说不清合并，说明算法还没有真正掌握。

七、实现代价、退化条件与替代方案

实现边界是：相等不构成严格逆序；计数最大 n(n-1)/2 需 long；排序结果必须正确写回。除了渐进时间，还要把递归栈、辅助数组、输入是否被修改以及最坏输入考虑进去。

检查项	面试中要回答的内容
基本情况	规模 0 或 1 时如何直接返回
规模缩小	每次递归是否严格靠近基本情况
合并正确性	子解怎样推出原问题答案
资源代价	递归深度、辅助结构与数据复制
退化保护	随机化、阈值切换、预排序或迭代改写

测试至少覆盖最小规模、奇偶长度、全部相等、严格有序/逆序、极端偏斜划分和会触发最大计数或溢出的数据。若存在更直接的线性算法、堆算法或动态规划，还要说明分治方案的教学价值与工程取舍。

八、常见误区与追问

误区：合并后再逐对比较也能 O(n log n)。 若跨半仍逐对比较会回到 O(n²)。
误区：遇到右值较小时只加 1。 左段有序，当前及其后所有左值都更大，应批量加剩余数量。
误区：相等元素算逆序对。 定义通常要求 i<j 且 a[i]>a[j]。
追问：为什么不会重计？ 每对元素只在它们首次分属当前左右半区的递归层被统计。
追问：树状数组如何做？ 离散化后从右向左查询更小值频次并更新。
追问：归并法的额外空间？ 数组实现通常 O(n)，递归栈 O(log n)。

九、加强记忆

逆序对 = i<j 且 a[i]>a[j]。用归并排序求：把逆序对分成左半内部、右半内部、跨半三类，递归数前两类、合并时数跨半。合并的诀窍是——左右已各自有序，当 a[i]>a[j] 时左半 [i..mid] 全都 > a[j]，一次加 mid−i+1；相等用 <= 取左不计数。时间 O(n log n)、空间 O(n)，计数用 long 防溢出。另有等价的树状数组解法。

简化版

详细版