Java implementation to find the number of inversions in a given array.

Inversions.java

public class Inversions {
  public static long calcInversions(int[] input) {
  		if (input.length == 1) {
  			return 0;
  		}
  		
  		long numberOfInversions = 0;		
  		int halfLength = input.length / 2;
  		int leftLength = halfLength;
  		int rightLength = halfLength;
  		if (input.length % 2 != 0) {
  			leftLength = halfLength + 1; 
  		}
  		int[] leftHalf = new int[leftLength];
  		int[] rightHalf = new int[rightLength];
  		
  		for (int i = 0; i < leftLength; i++) {
  			leftHalf[i] = input[i];
  		}
  		for (int i = leftLength, j = 0; i < input.length; i++, j++) {
  			rightHalf[j] = input[i];
  		}
  		
  		numberOfInversions += calcInversions(leftHalf);
  		numberOfInversions += calcInversions(rightHalf);
  		
  		numberOfInversions += merge(leftHalf, rightHalf, input);
  		
  		return numberOfInversions;
  		
  	}
  
  	private static long merge(int[] leftHalf, int[] rightHalf, int[] output) {
  		int i = 0;
  		int j = 0;
  		int outIndex = 0;
  		long numberOfInversions = 0;
  		
  		while (outIndex < output.length) {
  			if (j >= rightHalf.length || (i < leftHalf.length && leftHalf[i] < rightHalf[j])) {
  				output[outIndex] = leftHalf[i];
  				i++;				
  			} else {
  				output[outIndex] = rightHalf[j];
  				j++;
  				numberOfInversions += leftHalf.length - i;
  			}
  			outIndex++;
  		}
  		
  		return numberOfInversions;
  	}
}