MergeSort and Counting Inversions.

MergeSort.java

	
	private static int nInversions=0;
	
	/** call helper function here */
  public static void sort(Comparable[]a){
		int lo=0,hi=a.length-1;
		Comparable [] aux = new Comparable[a.length];
		nInversions = sort(a,aux,lo,hi);
 	}
 	
 		/** recursively divide []a to a/2 size and merge  */
 	private static int sort(Comparable []a, Comparable[]aux, int lo, int hi){
		if(hi<=lo) return 0;
		int mid = lo+(hi-lo)/2;
		int lin = sort(a,aux,lo,mid);
		int rin= sort(a,aux,mid+1,hi);
		int in = merge(a,aux,lo,mid,hi);
		return in+rin+lin;
	}
		/** merge from array [lo .. mid,mid+1.. hi] */
	private static int merge(Comparable []a, Comparable[]aux, int lo, int mid, int hi){
		for(int k=lo;k<=hi;k++){
			aux[k]=a[k];
		}
		int i=lo, j=mid+1,cin=0;
		for(int k=lo;k<=hi;k++){
			if(i>mid)
				a[k]=aux[j++];
	 		else if(j>hi)
				a[k]=aux[i++];							
			else if(less(aux[j],aux[i]))
				a[k]=aux[j++];
			else {
				cin=j-i;
				a[k]=aux[i++];
			}
		}
		return cin;
	}
	
	/* main function call */
	public static void main(String[] args) {
		Comparable [] a= {1,5,17,13,2};
		System.out.println("Before sort:");
		printArray(a);
		sort(a);
		System.out.println("Number of inversions is "+nInversions);
		System.out.println("After sort:");
		printArray(a);
 	}
 	
 	private static void printArray(Comparable[]a){
 		for(int i=0;i<a.length;i++)
 			System.out.println(a[i]+"\t");
 			System.out.println("");
 	}