public class quickSort extends Timer

{

 public static void main(String[] args)
    {
	int arrayLength = 1048576;
	
	System.out.printf( "Array of length %d\n", arrayLength );
	
	Timer timer = new Timer ();
	
	java.util.Random r = new java.util.Random();
	int[] myArray =  new int [arrayLength];
	for (int i=0; i<arrayLength; i++) myArray[i] = r.nextInt();
	
	quicksort(myArray,0,myArray.length-1);
	for (int i = 0; i < myArray.length; i++)
		{ System.out.printf("%d,",myArray[i]); }
		
	timer.stop();
	
	double n = (double)arrayLength;
	n = n * Math.log(n);
	System.out.println( "n log(n) = " + (new Double(n)).toString() );
	}

public static void quicksort (int[] a)
	{
	quicksort(a, 0, a.length-1);
	}
 
 private static void quicksort (int[] a, int left, int right)
	{
	if ( left >= right )				//list is empty
	return;
	int m = partition(a, left, right); //make partition and sort recursively
	quicksort(a,left,m-1);
	quicksort(a,m+1,right);
	}
 
//partition the array from l+1 to r with pivot a[l] 
private static int partition (int[] a, int left, int right)
	{
	int i=left+1;					//define left pointer
	int j=right;					//define right pointer
	int p = a[left];				//pivot element
	while (i<=j)				//move pointer to center or swap if on wrong sides
		{ 
		if (a[i]<=p) i++;
		else if (a[j]>p) j--;
		else swap(a,i,j);
		}
	swap(a,left,j);					//swap pivot element between partitions
	return j;
	}							//return position of pivot element

//swap two elements in the array
private static void swap (int[] a, int i, int j)
	{ 
	int h = a[i];
	a[i] = a[j];
	a[j] = h; }
	}