/**
 * Class MergeSort. Implements the mergesort algorithm.
 *
 * @author Philipp Bolliger <br>
 * Informatik II - FS2009 <br>
 * Uebungsserie 10
 */
public class MergeSort {

	/**
	 * Mergesort algorithm.
	 * @param a an array of Comparable items.
	 */
	public static void mergeSort( Comparable [] a) {
		Comparable [] tmpArray = new Comparable[ a.length ];
		mergeSort( a, tmpArray, 0, a.length - 1 );
	}

	/**
	 * Internal method that makes recursive calls.
	 * @param a an array of Comparable items.
	 * @param tmpArray an array to place the merged result.
	 * @param left the left-most index of the subarray.
	 * @param right the right-most index of the subarray.
	 */
	private static void mergeSort( Comparable [] a, Comparable [] tmpArray, int left, int right) {
		if( left < right ){
			int center = (left + right) / 2;
			mergeSort(a, tmpArray, left, center );
			mergeSort( a, tmpArray, center+1, right);
			merge(a, tmpArray, left, center+1, right);
		}
	}

	private static void merge( Comparable [] a, Comparable [] tmpArray, int leftPos, int rightPos, int rightEnd) {
		int leftEnd = rightPos-1;
		int tmpPos = leftPos;
		int numElements = rightEnd - leftPos + 1;

		//Main loop
		while( leftPos <= leftEnd && rightPos <= rightEnd )
			//if object left is smaller then object at right pos
			if( a[ leftPos ].compareTo(a[ rightPos ]) < 0 )
				//
				tmpArray[ tmpPos++ ] = a[ rightPos++ ];
			else
				tmpArray[ tmpPos++ ] = a[ leftPos++ ];

		while( leftPos <= leftEnd )  //Copy rest of first half
			tmpArray[ tmpPos++ ] = a[ leftPos++ ];

		while( rightPos <= rightEnd )  //Copy rest of right half
			tmpArray[ tmpPos++ ] = a[ rightPos++ ];

		//Copy tmpArray back
		for( int i = 0; i < numElements; i++, rightEnd--)
			a[ rightEnd ] = tmpArray[ rightEnd ];
	}
}