Find number of inversions in a given list of integers

Inversion: pairs (i,j) of array indices with i<j and A[i] > A[j] 

The task is to find number of such pairs.

A) Brute force way is to start from the left and find out for each element, the number of pairs. At the end, we will have the total count.

B) Another way is to use device-and-conquer paradigm. Divide the list into two. Keep dividing till we reach single element. Then the merge comes for sorting the array. While merging, if the left element is more than the element from the right then we know that the all the elements in the right are smaller than the bigger element, hence we have that count of inversions.

I have outlined the procedure on paper as below:

The code for the same is below:

int MergeAndCount(int *arr, int l, int m, int r);

int MergeSort(int *arr, int l, int r)

{

if (arr == NULL) return 0;

if (l >= r) return 0;

int mid = (l+r)/2;

int left = MergeSort(arr, l, mid);

int right = MergeSort(arr, mid + 1, r);

int mc = MergeAndCount(arr, l, mid, r);

return (left + right + mc);

}

int MergeAndCount(int *arr, int l, int m, int r)

{

if (arr == NULL) return 0;

if (l >= r) return 0;

int icounter = 0;

int tl = l;

int tm = m + 1;

int tr = r;

int temp = 0;

int *tarr = new int [r - l + 1];

while (tl <=m && tm <= r)

{

if (arr[tl] <= arr[tm])

{

tarr[temp++] = arr[tl++];

}

else

{

icounter += m - tl + 1;

tarr [temp++] = arr[tm++];

}

}

while (tl <= m)

tarr[temp++] = arr[tl++];

while (tr <= r)

tarr[temp++] = arr[tr++];

// Now copy back the array

temp = 0;

while (l <= r)

{

arr[l++] = tarr[temp++];

}

delete tarr;

return icounter;

}

I hope it helps.