Inversion count

gistfile1.c

totalInversions = 0

countInversions (array, start, end)
	if (start < end)
		int mid = (start + end)/2
		countInversions(array, start, mid)
		countInversion(array, mid+1, end)
		merge(array, start, mid, end)
	// else do nothing	
	
merge(a, low, mid, high)
	i = low, j = mid+1
	
	aux = new_array_with_size:(high-low+1) // separate array to copy sorted array into
	
	count = 0
	k = 0
	while (i <= mid && j <= high)
		if (a[i] <= a[j])
			aux[k++] = a[i++]
		else
			aux[k++] = a[j++]
			count++ // that's an inversion
	
	if (i < mid)
		leftover = mid - i
		count *= leftover // the original inversion count * leftover in first half
		while (i <= mid)
			aux[k++] = a[i++]
	else if (j < high)
		while (j <= high)
			aux[k++] = a[j++]
	
	totalInversions += count
	// copy aux back to a starting from low
	copy (aux, a(low))