// QuickSort, snipped and adapted by Prof. Golden G. Richard III 
// from the JDK1.1.1 sample applets

class QuickSort {
    static void IntegerQuickSort(int a[], int lo0, int hi0) {
	int lo = lo0;
	int hi = hi0;
	int mid;
	
	if ( hi0 > lo0) {
	    
	    /* Arbitrarily establishing partition element as the midpoint of
	     * the array.
	     */
	    mid = a[ ( lo0 + hi0 ) / 2 ];
	    // loop through the array until indices cross
	    while( lo <= hi ) {
		/* find the first element that is greater than or equal to 
		 * the partition element starting from the left Index.
		 */
		while( ( lo < hi0 ) && ( a[lo] < mid )) {
		    ++lo;
		}
		
		/* find an element that is smaller than or equal to 
		 * the partition element starting from the right Index.
		 */
		while( ( hi > lo0 ) && ( a[hi] > mid )) {
		    --hi;
		}
		
		// if the indexes have not crossed, swap
		if( lo <= hi ) {
		    swap(a, lo, hi);
		    ++lo;
		    --hi;
		}
	    }
	    /* If the right index has not reached the left side of array
	     * must now sort the left partition.
	     */
	    if( lo0 < hi ) {
		IntegerQuickSort( a, lo0, hi );
	    }
	    /* If the left index has not reached the right side of array
	     * must now sort the right partition.
	     */
	    if( lo < hi0 ) {
		IntegerQuickSort( a, lo, hi0 );
	    }
	}
    }
    
    static private void swap(int a[], int i, int j) {
	int T;
	T = a[i]; 
	a[i] = a[j];
	a[j] = T;
    }
}