countinversions.txt

#include <bits/stdc++.h>
int merge(long long int arr[],long long int temp[],int left,int mid,int right)
{
    int inv_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++];
            inv_count = inv_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 inv_count;
}
int mergesort(long long *arr,long long *temp,int low,int high){
    int mid=(low+high)/2;
    int count=0;
    if(high>low){
        count+=mergesort(arr,temp,low,mid);
        count+=mergesort(arr,temp,mid+1,high);
    
    count+=merge(arr,temp,low,mid+1,high);
    }
    return count;
    
}
long long getInversions(long long *arr, int n){
    // Write your code here.
    long long int temp[n];
    int ans=mergesort(arr,temp,0,n-1);
    return ans;
}