Algorithm: Counting inversions

inversion.c

//find number of inversions in a list
//inversion: number of (i,j) pairs where a[i] > a[j] and i < j

int merge(int* a, int n);
int countInversion(int* a, int n);

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define NUM_ELEMENTS_IN(t) (sizeof(t)/sizeof(*t))


int main(int argc, char const *argv[])
{
	int a[] = {3,2};
	int i, inversion_count = 0;
	
	inversion_count =  countInversion(a,NUM_ELEMENTS_IN(a));
	printf("Inversion count: %d\n",inversion_count);

	return 0;
}

int countInversion(int* a, int n){
	if( n <= 1 ){
		return 0;
	}

	//inversions come from first half, second half and merge of first and second halves
	return countInversion(a, n/2 ) + countInversion(a + n/2, n - n/2) + merge(a, n );
}


//if an element from second half of the list comes before an element from the first half
//there are inversions for that element that total to number of elements remaining in the first half of the list
int merge(int* a, int n){
	int i,k = 0,m = 0;
	int inversion_count = 0;

	int* temp = (int*)malloc(sizeof(int) * n);

	for (i = 0; (i < n) && (k < n/2) && (m < (n-n/2)) ; ++i)
	{

		if( a[k] < a[n/2+m]){

			temp[i] = a[k];
			k++;
		}else{
			temp[i] = a[n/2+m];
			m++;
			inversion_count += (n/2 - k);
		}
	}


	if( k < n/2 ){
		for( ;k < n/2;k++ ){
			temp[i++] = a[k];
		}
	}else if( m < (n-n/2)){
		for(; m < (n-n/2); m++){
			temp[i++] = a[n/2+m];
		}
	}

	memcpy(a,temp,sizeof(int) * n);
	free(temp);

	return inversion_count;
}