Design and Analysis of Algorithms

// C program to Count 
// Inversions in an array 
// using Merge Sort 
#include <stdio.h> 
#include <stdlib.h> 

long _mergeSort(long arr[], long temp[], long left, long right); 
long merge(long arr[], long temp[], long left, long mid, long right); 

/* This function sorts the input array and returns the 
number of inversions in the array */
long mergeSort(long arr[], long array_size) 
{ 
	long* temp = (long*)malloc(sizeof(long) * array_size); 
	return _mergeSort(arr, temp, 0, array_size - 1); 
} 

/* An auxiliary recursive function that sorts the input array and 
returns the number of inversions in the array. */
long _mergeSort(long arr[], long temp[], long left, long right) 
{ 
	long mid, inv_count = 0; 
	if (right > left) { 
		/* Divide the array longo two parts and call _mergeSortAndCountInv() 
	for each of the parts */
		mid = (right + left) / 2; 

		/* Inversion count will be the sum of inversions in left-part, right-part 
	and number of inversions in merging */
		inv_count += _mergeSort(arr, temp, left, mid); 
		inv_count += _mergeSort(arr, temp, mid + 1, right); 

		/*Merge the two parts*/
		inv_count += merge(arr, temp, left, mid + 1, right); 
	} 
	return inv_count; 
} 

/* This funt merges two sorted arrays and returns inversion count in 
the arrays.*/
long merge(long arr[], long temp[], long left, long mid, long right) 
{ 
	long i, j, k; 
	long inv_count = 0; 

	i = left; /* i is index for left subarray*/
	j = mid; /* j is index for right subarray*/
	k = left; /* k is index for resultant merged subarray*/
	while ((i <= mid - 1) && (j <= right)) { 
		if (arr[i] <= arr[j]) { 
			temp[k++] = arr[i++]; 
		} 
		else { 
			temp[k++] = arr[j++]; 

			/*this is tricky -- see above explanation/diagram for merge()*/
			inv_count = inv_count + (mid - i); 
		} 
	} 

	/* Copy the remaining elements of left subarray 
(if there are any) to temp*/
	while (i <= mid - 1) 
		temp[k++] = arr[i++]; 

	/* Copy the remaining elements of right subarray 
(if there are any) to temp*/
	while (j <= right) 
		temp[k++] = arr[j++]; 

	/*Copy back the merged elements to original array*/
	for (i = left; i <= right; i++) 
		arr[i] = temp[i]; 

	return inv_count; 
} 

/* Driver program to test above functions */
int main() 
{ 
	long n, i;
    scanf("%ld",&n);
    long arr[n]; 
    for(i=0; i<n; i++)
    scanf("%ld",&arr[i]);

    printf("Number of inversions are %ld.\n",mergeSort(arr,n));
	return 0; 
}