如何用归并排序统计数组中的逆序对？

简化版

逆序对是满足 i < j 且 nums[i] > nums[j] 的二元组。

可以用归并排序统计。递归统计左半部分和右半部分的逆序对，再在合并两个有序数组时统计跨左右两边的逆序对。

当左边当前元素大于右边当前元素时，左边从当前指针到末尾的所有元素都大于右边当前元素，因此一次可以加上这段数量。

详细版

归并排序统计逆序对的关键在合并阶段。

左右两边已经有序：

left:  2, 4, 6
right: 1, 3, 5

如果 left[i] > right[j]，因为 left 已经有序，所以：

left[i], left[i+1], ..., left[end]

都大于 right[j]。

于是逆序对数量增加：

mid - i + 1

整体复杂度是 O(n log n)。

完整版教学

1. 什么是逆序对

逆序对表示数组中两个元素的相对顺序和升序要求相反。

定义是：

i < j 且 nums[i] > nums[j]

例如：

[3, 1, 2]

逆序对有 (3,1) 和 (3,2)，数量是 2。

2. 暴力方法为什么慢

最直接的方法是枚举所有二元组：

for i in 0..n-1:
  for j in i+1..n-1:
    if nums[i] > nums[j]:
      count++

复杂度是 O(n^2)。

当 n 很大时不可接受。

3. 归并排序为什么能统计

归并排序把数组分成左右两半。

逆序对可以分成三类：

类型	位置
左半内部逆序对	递归统计
右半内部逆序对	递归统计
跨左右逆序对	合并时统计

前两类交给递归，最关键的是第三类。

4. 合并阶段如何一次统计多个

左右两边已经分别有序。

如果：

left[i] > right[j]

那么由于 left[i..end] 都不小于 left[i]，它们都大于 right[j]。

所以可以一次增加：

left.length - i

而不是一个个数。

归并统计逆序对的效率来自“有序性让一次比较贡献一批答案”。

5. 伪代码怎么写

合并时可以这样写：

merge(left, right):
  i = 0, j = 0
  while i < left.length and j < right.length:
    if left[i] <= right[j]:
      output left[i]
      i++
    else:
      count += left.length - i
      output right[j]
      j++

注意相等时不算逆序对，所以用 <= 先取左边。

6. 为什么相等不算

逆序对要求：

nums[i] > nums[j]

如果两个值相等，不满足大于。

因此合并时遇到 left[i] <= right[j]，应该先放左边，不增加计数。

这也让合并过程保持稳定。

7. 复杂度和溢出问题

归并排序层数是 log n，每层合并总共处理 n 个元素，所以时间是：

O(n log n)

逆序对数量最大可能是：

n * (n - 1) / 2

如果 n 很大，结果可能超过 int，应使用 long。

8. 常见误区与追问

• 误区：逆序对只能暴力枚举。 归并排序可以在 O(n log n) 内统计。
• 误区：相等元素也算逆序对。 定义要求严格大于，相等不算。
• 误区：合并后再统计跨区间。 跨区间统计要利用合并时左右有序的状态。
• 追问：为什么能加 left.length - i？ 因为左半剩余元素都大于当前右半元素。
• 追问：结果类型为什么可能要 long？ 逆序对最大数量是二次级，可能超过 32 位整数。