/**
* Class MergeSort. Implements the mergesort algorithm.
*
* @author Philipp Bolliger
* Informatik II - FS2009
* 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 ];
}
}