# 7-liner C++ Merge Sort (detailed explanation)

• 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:

1. Pair index `(i,j)` in first half of array, i.e., both `i, j` in range `[0,N/2)`.
2. Pair index `(i,j)` in second half of array, i.e., both `i, j` in range `[N/2,N)`.
3. 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:

1. Cases 1 and 2 reduce to sub-problems with half size of the original size `N`.
2. 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
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.