题解 | #数组中的逆序对#

递归排序求逆序对

mergeSort() 函数有两个作用：

1. 归并排序：拆分 -> 通过临时数组 tmp 排序 -> 将排序后的结果 tmp 放回原数组(tmp 从 0 开始将其放到原数组 data 从 l 开始到 r)
2. 返回值就是区间内 [l, r] 逆序对的数量

什么时候形成逆序对？

当 $data[i]>data[j],i\in [l,mid],j\in [mid+1,r]data[i]\; >\; data[j],\; i\; \backslash in\; [l,\; mid],\; j\; \backslash in\; [mid\; +\; 1,\; r]$ 的时候说明 (i, j) 是一个逆序对，同时 i 和 [mid + 1, j - 1] 中的每个数都构成逆序对。累积求出左区间和右区间所有的逆序对 res。