We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Merge Sort: Counting Inversions
  2. Discussions

Merge Sort: Counting Inversions

  • shounak647
     + 0 comments

    C++ solution. Solving this by merge sort is probably the quickest way, as it is done in O(nlogn) time, as opposed to other methods most of which run in O(n^2).

    An addition to the merge sort algorithm made specifically for this question is that we need to keep track of the number of swaps made in the algorithm.

    vector<int> merge_sort(vector<int> arr, long& swapCount) {
    if(arr.size() <= 1) return arr;
    
    size_t mid = arr.size() / 2 - 1;
    
    vector<int> left = vector<int>(arr.begin(), arr.begin()+mid+1);
    vector<int> right = vector<int>(arr.begin()+mid+1, arr.end());
    
    left = merge_sort(left, swapCount);
    right = merge_sort(right, swapCount);
    
    vector<int> res;
    
    int l = 0, r = 0;
    
    while(l < left.size() || r < right.size()) {
        if((l < left.size() && r < right.size())) {
            if(left[l] > right[r]) {
                swapCount += left.size()-l;
                res.push_back(right[r]);
                r++;
            } else {
                res.push_back(left[l]);
                l++;
            }
        } else if(l < left.size()) {
            res.push_back(left[l]);
            l++;
        } else {
            res.push_back(right[r]);
            r++;
        }
    }
    
    return res;
}

long countInversions(vector<int> arr) {
    long swapCount = 0;
    merge_sort(arr, swapCount);
   
   return swapCount;
}