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


  • 1

    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
        }
    

Log in to reply
 

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