public class mergeSort {
	public static void domergeSort( Comparable [] a, Comparable [] tmp, 
									int left, int right){
		if( left < right){
			int center = (left + right) / 2;
			domergeSort(a,tmp,left,center);
			domergeSort(a,tmp,center+1,right);
			merge(a,tmp,left,center+1,right);
		}
	}
	private static void merge( Comparable [] a, Comparable [] tmp, 
								int leftPos, int rightPos, int rightEnd ){
		int leftEnd = rightPos - 1;
		int tmpPos = leftPos;
		int numElement = rightEnd - leftPos + 1;
		while( leftPos <= leftEnd  &&  rightPos <= rightEnd){
			if( a[leftPos].compareTo(a[rightPos]) <= 0){
				tmp[tmpPos] = a[leftPos];
				tmpPos++;
				leftPos++;
			}else{
				tmp[tmpPos] = a[rightPos];
				tmpPos++;
				rightPos++;
			}
		}
		// rest of left
		while( leftPos <= leftEnd){
			tmp[tmpPos] = a[leftPos];
			tmpPos++;
			leftPos++;
		}
		// rest of right
		while( rightPos <= rightEnd){
			tmp[tmpPos] = a[rightPos];
			tmpPos++;
			rightPos++;
		}
		// copy tmp to a
		for( int i=0; i<numElement; i++, rightEnd--)
			a[rightEnd] = tmp[rightEnd];
	}
	public static void printArray( Comparable [] a){
		for( int i=0; i<a.length; i++)
			System.out.print(a[i] + " ");
		System.out.println();
	}
	// test mergeSort
	public static void main( String [] args){
		Comparable [] array = new Comparable[10];
		Comparable [] tmp = new Comparable[10];
		for(int i=0; i<array.length; i++)
			array[i] = array.length-i;
		printArray(array);
		domergeSort(array,tmp,0,array.length-1);
		printArray(array);
	}
}