This is basically just a minor rewritten of @StefanPochmann 's merge sort solution as I don't see how it can be shortened anymore.

Actually, it took me a while to realize how merge sort could be applicable to this problem, so just add my explanation below if it could clarify the algorithm for you.

**Key Observation:** Any *important reverse pair* `(i,j)`

of array `nums[i=0:N-1]`

must be in one the of following three cases:

- Pair index
`(i,j)`

in first half of array, i.e., both`i, j`

in range`[0,N/2)`

. - Pair index
`(i,j)`

in second half of array, i.e., both`i, j`

in range`[N/2,N)`

. - Pair index
`(i,j)`

in different halves of array, i.e.,`i`

in range`[0,N/2)`

and`j`

in`[N/2,N)`

.

Now here come the keys:

- Cases 1 and 2 reduce to sub-problems with half size of the original size
`N`

. - For Case 3, note that
**any**index in`[0,N/2)`

is bigger than**any**index in`[N/2,N)`

, so**the values' order in either half does not impact the count of reverse pairs**. So it is easy to count such pairs if both halves are sorted.

```
int reversePairs(vector<int>& nums) {
return sortCount(nums.begin(), nums.end());
}
// count reverse pairs in range [b,e) and then sort
int sortCount(vector<int>::iterator b, vector<int>::iterator e) {
if (e - b <= 1) return 0;
auto m = b+(e-b)/2;
int count = sortCount(b, m) + sortCount(m, e);
for (auto i = b, j = m; i<m && j<=e; *i/2.>*j? ++j : (count+=j-m, ++i))
if (j==e) { count += (m-i)*(e-m); break; }
return inplace_merge(b, m, e), count; // inplace_merge: merge two sorted segments
}
```