Inversion

Let A[1..n] be an array of n distinct numbers.If i < j and A[i] > A[j], then the pair (i,j) is called an inversion of A.
Consider the array (2,3,8,6,1). Inversions in array are (8,6), (2,1), (3,1) , (8,1), (6,1).

Write program to count the number of inversion in array.

/*
 * CountInverion0 : This is modified version of insertion sort. Time Complexity : O(n^2)
 */
int CountInversion0(int a[], int n)
{
    int i,j,count=0;
    for(i=1; i<n; i++) {
             for(j=0; j<i; j++)
                      if(a[j] > a[i])
                              count++;
    }
    return count;
}

/*
 * CountInversion1 : Modifed version of Merge sort. Uses Divide and Conquer Methodlogy.
 * TimeComplexity: O(n*log(n)).
 */
int CountInversion1(int A[], int start, int end)
{
    int i,x,y;
    int z=0;
    if((end-start) == 0) return 0;
    else if(start < end) {
        i = (start+end)/2;
        x = CountInversion1(A, start , i);
        y = CountInversion1(A, i+1, end);
        z = CountSplitInversion(A,start,end,i);
        return x+y+z;
    }
}
/*
 * Helper function: sorts array and also count the number of inversion.
 * Hint : in case of merge sort, while merging if we copy the number from 2nd array to array,
 * number of elements lefts in first array adds to the number of inversions.
 */
int CountSplitInversion(int a[],int start, int end, int div)
{
    int i,j,k,lc = (div-start)+1,rc = (end-div),*l,*r,count = 0;
    l = (int *) malloc(sizeof(int) * (lc+1));
    r = (int *) malloc(sizeof(int) * (rc+1));
    for(i=0; i < lc; i++)
        l[i] = a[start + i];
    for(i=0; i < rc; i++)
        r[i] = a[div+i+1];
    for(k=start,i=0,j=0; k <= end && (i < lc) && (j <rc) ;k++)
    {
        if(l[i] <= r[j]) {
            a[k] = l[i]; i++;
        }
        else {
            a[k] = r[j]; j++;
            count +=  (lc - i);
        }
    }
    if(i < lc) {
        for(;k<=end && i<lc ;k++)
            a[k] = l[i];
    }
    if(j < rc) {
        for(;k<=end && j<rc ;k++)
            a[k] = r[j];
    }
    return count;
}