public class quickSort {
	private static void swapRef( Comparable [] a, int i, int j){
		Comparable tmp;
		tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;
	}
	private static Comparable median3( Comparable [] a, int left, int right){
		int center = (left + right)/2;
		if( a[center].compareTo(a[left]) < 0 )
			swapRef(a,left,center);
		if( a[right].compareTo(a[left]) < 0 )
			swapRef(a,left,right);
		if( a[right].compareTo(a[center]) < 0)
			swapRef(a,center,right);
		// place pivot at pos right-1
		swapRef(a,center,right-1);
		return a[right-1];
	}
	public static int partition( Comparable [] a, int left, int right){
		Comparable pivot = median3(a,left,right);
		// partitioning
		int i=left, j=right-1;
		for(;;){
			i++;
			while( a[i].compareTo(pivot) < 0 )
				i++;
			j--;
			while( a[j].compareTo(pivot) > 0 )
				j--;
			if( i < j )
				swapRef(a,i,j);
			else
				break;
		}
		swapRef(a,i,right-1);	// restore pivot
		return i;
	}
	public static void doquickSort( Comparable [] a, int left, int right){
		int i;
		if(left < right){
			i = partition(a,left,right);
//			printArray(a);
//			System.out.println("pivot at "+i);
			doquickSort(a,left,i-1);
			doquickSort(a,i+1,right);
		}
	}
	public static void printArray(Comparable [] a){
		for(int i=0; i<100; i++)
			System.out.print(a[i] + " ");
		System.out.println();
	}
	// test quickSort
	public static void main( String [] args){
		Comparable [] array = new Comparable[1000000];
		for( int i=0; i<array.length; i++)
			array[i] = array.length-i;
//		printArray(array);
		doquickSort(array,0,array.length-1);
		printArray(array);
	}
}