code

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

int merge(int a[], int l, int m, int r){
	vector<int> x( a + l, a + m + 1);
	vector<int> y( a + m + 1, a + r + 1);
	int i = 0, j = 0;
	int count = 0;
	while(i < x .size() && j < y.size()){
		if(x[i] <= y[j]){
			a[l] = x[i];
			++l;
			++i;
		}
		else{
			count += x.size() - i;
			a[l] = y[j];
			++l;
			++j;
		}
	}
	while(i < x.size()){
		a[l] = x[i];
		++l;
		++i;
	}
	while(j < y.size()){
		a[l] = y[j];
		++l;
		++j;
	}
	return count;
} 
int mergeSort(int a[], int l, int r){
	int dem = 0;
	if(l < r){
		int m = (l + r)/2;
		dem += mergeSort(a, l, m); // sl cap nghich the ben trai
		dem += mergeSort(a, m + 1, r); // sl cap nghich the ben phai
		dem += merge(a, l, m, r); // sl cap nghich the 1 phan tu ben trai 1 phan tu ben phai
	}
	return dem;
}
int main()
{
	int a[] = { 1, 20, 6, 4, 5 };
    int n = sizeof(a) / sizeof(a[0]);
    int ans = mergeSort(a, 0 ,n-1);
    cout << " Number of inversions are " << ans;
	return 0;
}