Count Inversions

https://www.codingninjas.com/studio/problems/count-inversions_615?leftPanelTab=0


#include <bits/stdc++.h> 

long long merge(long long *arr,int low,int mid,int high){
    int left=low;
    int right=mid+1;
    long long cnt=0;
    vector<int> temp;
    while((left<=mid) && (right<=high)){
        if(arr[left]<arr[right]){
            temp.push_back(arr[left]);
            left++;
        }
        else{
            temp.push_back(arr[right]);
            cnt+=(mid-left+1);
            right++;
        }
    }
    while(left<=mid){
        temp.push_back(arr[left]);
        left++;
    }
    while(right<=high){
        temp.push_back(arr[right]);
        right++;
    }
    for(int i=left;i<=right;i++){
        arr[i]=temp[i-low];
    }
    return cnt;
}

long long mergeSort(long long *arr,int left,int right){
    int mid=0;
    long long cnt=0;
    if(left<right){
        mid=(left+right)/2;
        cnt+=mergeSort(arr,left,mid);
        cnt+=mergeSort(arr,mid+1,right);
        cnt+=merge(arr,left,mid,right);
    }
    return cnt;
}


long long getInversions(long long *arr, int n){
    long long total=mergeSort(arr,0,n-1);
    return total;
}