Given an array of arbitrary integers, count the no. of inversion pairs where inversion pair is defined as A[i] > A[j] and i < j .

/*

 * The idea is to use Merge sort since it takes o(nlogn) time.

 * Merge function will not only merge the subarrays but select inversion pairs also.
 * If an array is divided into left and right halves.
 * If any element is copied into merge array before all the elements of left sub-array is copied into merge array then it is an inversion pair.
 * This task is extra apart from merging but still merge function performs in o(n) time preserving the overall o(nlogn) time.
 */

#include <iostream.h>

using namespace std;

void MergeSort(int [] , int , int);

void MergeAndCount(int [], int , int , int );

void display(int a[] , int n)

{

     for(int i=0; i< n; i++)

             cout<<a[i]<<"  ";

}

void MergeSort(int array[], int low, int high)

{

     if(low < high)

     {

            int mid = (high+low)/2;

            MergeSort(array,low, mid);

            MergeSort(array,mid+1,high);

            MergeAndCount(array,low,mid,high);

     }

}

void MergeAndCount(int array[], int low, int mid, int high)

{

     int i= low, j = mid+1, k=0;

     int *c = new int[high-low+1];

     while(i <= mid && j <= high)

     {

             if(array[i] < array[j])

                         c[k++] = array[i++];

             else

             {

                 cout<<"\n( "<<array[i]<<" , "<<array[j]<<" ) ";

                 c[k++] = array[j++];

             }

     }

     while(i <= mid)

             c[k++] = array[i++];

     while(j <= high )

             c[k++] = array[j++];

     int s = 0;

     while( s < k)

     {

            array[s+low] = c[s];

            s++;

     }

     delete[] c;

}

int main()

{

    int array[] = {1,5,3,6,2,4};

    int length = sizeof(array)/sizeof(array[0]);

    MergeSort(array,0,length-1);

    display(array,length);

    system("pause");

}