Using merge sort in C++ with explanation


  • 0
    S

    The code is inspired by other posts on using merge sort.

    After having left, right sorted sub arrays, when merging, the count of "smaller on the right" of each number in right sub array won't change; while the count of "smaller on the right" of each number "L" in the left sub array will be increased by numbers that belong to right sub array end up before "L" in the merged queue -- it happens to be number of merged elements of right sub array during the process.

    '''
    class Solution {
    void mcount(vector<pair<int,int>>&pairs, int lo, int hi, vector<int>&res){
    if (hi==lo+1) return;
    int mid = (hi+lo)/2;

            mcount(pairs, lo, mid, res); 
            mcount(pairs, mid, hi, res);
            
            //-- merger sort and count.
            vector<pair<int,int>> tmp;
            int i=lo, j=mid;
            while (i<mid && j<hi) 
                if (pairs[i].first <= pairs[j].first) {
                    res[pairs[i].second]+= j-mid;
                    tmp.push_back(pairs[i++]);
                }
                else tmp.push_back(pairs[j++]);
            while(i<mid) {
                    res[pairs[i].second]+= j-mid;
                    tmp.push_back(pairs[i++]);
            }
            while (j<hi) tmp.push_back(pairs[j++]);
            for (auto& n:tmp) pairs[lo++] = n;
        };
    

    public:
    vector<int> countSmaller(vector<int>& nums) {
    if (nums.empty()) return {};
    vector<int> res(nums.size(), 0);

        //-- need to memorize the orignal index of each number
        vector<pair<int,int>> pairs;
        for (int i=0; i<nums.size(); i++) 
            pairs.push_back({nums[i], i});
        
        mcount (pairs, 0, pairs.size(), res);
        return res; 
    }
    

    };
    '''


Log in to reply
 

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