Inversion count

gistfile1.java

import java.util.Arrays;

public class InversionCount {
	public static void main(String[] args) {
		int[] input = { 2, 4, 1, 3, 5 };
		System.out.println("Inversion count :" + invCount(input));
	}

	private static int invCount(int[] arr) {
		if (arr.length < 2)
			return 0;
		int mid = arr.length / 2;
		int[] left = Arrays.copyOfRange(arr, 0, mid);
		int[] right = Arrays.copyOfRange(arr, mid, arr.length);

		return invCount(left) + invCount(right) + merge(arr, left, right);
	}

	private static int merge(int[] arr, int[] left, int[] right) {

		int i = 0, j = 0, count = 0;
		while (i < left.length || j < right.length) {
			if (i == left.length)
				arr[i + j] = right[j++];
			else if (j == right.length)
				arr[i + j] = left[i++];
			else if (left[i] <= right[j])
				arr[i + j] = left[i++];
			else {
				arr[i + j] = right[j++];
				count += left.length - i;
			}
		}
		return count;
	}

}