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

Sort by

recency

|

509 Discussions

|

  • 24BCS10374
     + 0 comments

    include

    include

    using namespace std;

    long long mergeAndCount(vector& arr, vector& temp, int left, int mid, int right) {

    long long inversion_count = 0;

int i = left;

int j = mid;

int k = left;



while (i <= mid - 1 && j <= right) {

    if (arr[i] <= arr[j]) {

        temp[k++] = arr[i++];

    } else {

        temp[k++] = arr[j++];

        inversion_count += (mid - i);

    }

}



while (i <= mid - 1) {

    temp[k++] = arr[i++];

}



while (j <= right) {

    temp[k++] = arr[j++];

}



for (i = left; i <= right; i++) {

    arr[i] = temp[i];

}



return inversion_count;

    }

    long long mergeSortAndCount(vector& arr, vector& temp, int left, int right) {

    long long inversion_count = 0;

if (left < right) {

    int mid = left + (right - left) / 2;



    inversion_count += mergeSortAndCount(arr, temp, left, mid);

    inversion_count += mergeSortAndCount(arr, temp, mid + 1, right);

    inversion_count += mergeAndCount(arr, temp, left, mid + 1, right);

}

return inversion_count;

    }

    long long countInversions(vector& arr) {

    int n = arr.size();

vector<int> temp(n);

return mergeSortAndCount(arr, temp, 0, n - 1);

    }

    int main() {

    int t;

cin >> t;



while (t--) {

    int n;

    cin >> n;

    vector<int> arr(n);

    for (int i = 0; i < n; i++) {

        cin >> arr[i];

    }

    cout << countInversions(arr) << endl;

}



return 0;

    }

  • Migueel0
     + 0 comments
    def countInversions(arr):
    def merge_sort_and_count(arr):
        if len(arr) <= 1:
            return arr, 0
        
        mid = len(arr) // 2
        left, left_inversions = merge_sort_and_count(arr[:mid])
        right, right_inversions = merge_sort_and_count(arr[mid:])
        
        merged, split_inversions = merge_and_count(left, right)
        
        total_inversions = left_inversions + right_inversions + split_inversions
        return merged, total_inversions
    
    def merge_and_count(left, right):
        res = []
        i = j = 0
        inversions = 0
        
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:  
                res.append(left[i])
                i += 1
            else: 
                res.append(right[j])
                j += 1
                inversions += len(left) - i  
        
        res.extend(left[i:])
        res.extend(right[j:])
        
        return res, inversions
    
    _, total_inversions = merge_sort_and_count(arr)
    return total_inversions

  • yonatanimm
     + 0 comments

    Java Solution

        public static long countInversions(List<Integer> arr) {
        int size = arr.size();
        AtomicLong atomicLong = new AtomicLong(0L);
        
        mergeSort(arr, 0, size, atomicLong);
        
        return atomicLong.get();
    }
    
    private static void mergeSort(List<Integer> arr, int firstIndex, int lastIndex, AtomicLong atomicLong){
        if(firstIndex >= lastIndex){
            return;
        }
        final int mediumIndex = firstIndex + ((lastIndex - firstIndex) / 2);
        if(mediumIndex == firstIndex){
            return;
        }
        mergeSort(arr, firstIndex, mediumIndex, atomicLong);
        mergeSort(arr, mediumIndex, lastIndex, atomicLong);
        merge(arr, firstIndex, mediumIndex, lastIndex, atomicLong);
    }
    
    private static void merge(List<Integer> arr, int firstIndex, int mediumIndex, int lastIndex, AtomicLong atomicLong){
        final List<Integer> firstList = arr.subList(firstIndex, mediumIndex).stream().collect(Collectors.toList());
        final List<Integer> secondList = arr.subList(mediumIndex, lastIndex).stream().collect(Collectors.toList());
        
        final int firstSize = firstList.size();
        final int secondSize = secondList.size();
        
        if(firstSize == 0 || secondSize == 0){
            return;
        }
        
        int i = 0, j = 0, k = firstIndex;
        while(i<firstSize && j < secondSize){
            int first = firstList.get(i);
            int second = secondList.get(j);
            if(first <= second){
                arr.set(k, first);
                i++;
            }
            else{
                arr.set(k, second);
                j++;
                atomicLong.addAndGet(firstSize-i);
            }
            k++;
        }
        
        while(i<firstSize){
            arr.set(k, firstList.get(i));
            i++;
            k++;
        }
        
        while(j < secondSize){
            arr.set(k, secondList.get(j));
            j++;
            k++;
        }
    }

  • dehaka
     + 0 comments

    O(n log(n))

    void merge(vector<int>& V, int left, int mid, int right, long& swaps) {
    vector<int> leftV(V.begin() + left, V.begin() + mid + 1), rightV(V.begin() + mid + 1, V.begin() + right + 1);
    int i = 0, j = 0, k = left;
    while (i < leftV.size() and j < rightV.size()) {
        if (leftV[i] <= rightV[j]) {
            V[k] = leftV[i];
            ++i;
        }
        else {
            V[k] = rightV[j];
            ++j;
            swaps = swaps + leftV.size() - i;
        }
        ++k;
    }
    while (i < leftV.size()) {
        V[k] = leftV[i];
        ++i;
        ++k;
    }
    while (j < rightV.size()) {
        V[k] = rightV[j];
        ++j;
        ++k;
    }
}

void merge_sort(vector<int>& V, int left, int right, long& swaps) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    merge_sort(V, left, mid, swaps);
    merge_sort(V, mid + 1, right, swaps);
    merge(V, left, mid, right, swaps);
}

long countInversions(vector<int>& arr) {
    long swaps = 0;
    merge_sort(arr, 0, arr.size() - 1, swaps);
    return swaps;
}

  • shounak647
     + 1 comment

    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;
}