inversionCount.cpp

#include <bits/stdc++.h>
using namespace std;


int merge(int a[], int s, int e){
 
 int mid=(s+e)/2;
 int i=s;
 int j=mid+1;
 int k=s;

 int temp[100000];

 int ct=0; //store cross inversions

 while(i<=mid && j<=e){
 if(a[i]<a[j]){
 temp[k++]=a[i++];
 }
 else{
 ct+=mid-i+1;
 temp[k++]=a[j++];
 }
 }

 while(i<=mid) temp[k++]=a[i++];
 while(j<=e) temp[k++]=a[j++];

 for(int i=s; i<=e; i++) a[i]=temp[i];

 return ct;

}

//using merge sort type algorithm
int mergeSort(int a[], int s, int e){
 if(s>=e) return 0;

 int mid=(s+e)/2;

 int x= mergeSort(a,s,mid);
 int y= mergeSort(a,mid+1,e);

 int z= merge(a,s,e);

 return x+y+z;
}


int main(){
 int n; cin>>n; 
 int arr[n]; 
 for(int i=0; i<n; i++) cin>>arr[i];

 int ans=mergeSort(arr,0,n-1);
 cout<<ans<<endl;
 

}