Quicksort

class Quicksort 
{
	
	public static void quicksort( Comparable [ ] a ) 
	{ 
		quicksort( a, 0, a.length - 1 ); 
	}
	
	private static final int CUTOFF = 10;
	
	public static void swapReferences( Object [ ] a, int index1, int index2 ) 
	{
		Object tmp = a[ index1 ];
		a[ index1 ] = a[ index2 ];
		a[ index2 ] = tmp;
	}

	private static void quicksort( Comparable [ ] a, int low, int high ) 
	{
		int middle;
		if( low + CUTOFF > high ) insertionSort( a, low, high );
		else 
		{
			// Sort low, middle, high
			middle = ( low + high ) / 2;
			
			if( a[middle].lessThan( a[ low ] ) ) 
				swapReferences( a, low, middle );
			
			if( a[high].lessThan( a[ low ] ) ) 
				swapReferences( a, low, high );
			
			if( a[high].lessThan( a[ middle ] ) ) 
				swapReferences( a, middle, high );

			// Place pivot at position high - 1
			swapReferences( a, middle, high - 1 );
			Comparable pivot = a[ high - 1 ];
			
			// Begin partitioning
			int i, j;
			for( i = low, j = high - 1; ; ) 
			{
				while( a[ ++i ].lessThan( pivot ) ) ;
				while( pivot.lessThan( a[ --j ] ) ) ;
				if( i < j ) swapReferences( a, i, j );
				else break;	
			}
			// Restore pivot
			swapReferences( a, i, high - 1 );
			quicksort( a, low, i - 1 ); // Sort small elements
			quicksort( a, i + 1, high ); // Sort large elements
		}
	}
}