Hey buddy!

As you well know, the program you've suggested here is great, reliable but there's a certain hitch. It runs with a time complexity of O(n^2). This might not seem like a big deal but when you're dealing with huge arrays with a large number of elements, it may cause performance issues.

The challenge here is finding the number of inversions in a permutation on n elements, but the trick is doing it within O(nlogn) worst-case time. A smart modification of the merge sort algorithm can be a real game changer here, and lucky for you, I tweaked it to our benefit here:

#include<stdio.h>

int merge(int arr[], int temp[], int left, int mid, int right);
int _mergeSort(int arr[], int temp[], int left, int right);
int inversionCount(int arr[], int n)

{

   int temp[n];
   return _mergeSort(arr, temp, 0, n - 1);
}

int _mergeSort(int arr[], int temp[], int left, int right)

{
   int mid, inv_count = 0;
   if (right > left) {
      mid = (right + left)/2;
      inv_count  = _mergeSort(arr, temp, left, mid);
      inv_count += _mergeSort(arr, temp, mid+1, right);
      inv_count += merge(arr, temp, left, mid+1, right);
   }

   return inv_count;
}

int merge(int arr[], int temp[], int left, int mid, int right)

{
   int i, j, k;
   int inv_count = 0;
   i = left;   

   j = mid;
   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 main(int argv, char **args)
{
   int arr[] = {4, 1, 3, 2};
   printf("Number of inversions are %d \n", inversionCount(arr, sizeof(arr)/sizeof(arr[0])));
   return 0;
}

As you asked, this piece of code will help you get the inversion count in an array and that too in O(nlogn) time complexity, thanks to merge sort.

And before I close the lid on this one, I hope you are doing alright handling the pointers and recursion here. The inversion counting part is the only trick in this pudding. Remember, for every i in the first array, if j is an element in the second array, all elements after i in the first subarray and j in the second subarray will form valid inversions. So simply add up (mid – i) inversions for all such valid i and j!

This should help you out. Let me know if you need me to break it down more.

Happy Coding!

somesh

Comments (13)