class quicksort extends basic {

    static String printarray (int[] array) {
	String txt = "";
	for (int i=0; i < array.length-1; i++) {
	    txt = txt+array[i]+" ";
	}
	if (array.length > 0) txt = txt+array[array.length - 1];

	return txt;
    }

    static void report (String txt) throws Exception {
	output out = new output();
	out.writeln(txt);
	out.close();
    }


    // quicksort: algorithm based no Gosling's variant from nist
    static void quicksort (int[] array, int from, int upto) 
	throws Exception {
        // print details of call
	report("calling qs ("+printarray(array)+", "+from+", "+upto+")");

	if (from < upto) {


	    // make the pivot value middle of array
	    int pivot = array[(from+upto)/2];

	    // set up two pointers into the array
	    int lower = from, upper = upto;
        
	    while (lower <= upper) {
		// first move lower up over small elements
		while ((array[lower] < pivot) && (lower < upto)) lower++;
		// otherwise move upper down over large elements
		while ((array[upper] > pivot) && (upper > from)) upper--;
                // if pointers haven't crossed
                if (lower <= upper) {
		    int tmp = array[upper];
		    array[upper] = array[lower];
		    array[lower] = tmp;
		    lower++;
		    upper--;
		}
	    }

            report("doing qs(..,., "+from+", "+upto+") with current "+printarray(array));

	    if (from < upper) quicksort(array,from,upper);
	    if (lower < upto) quicksort(array,lower,upto);

	}
	report("leaving qs (..., "+from+", "+upto+") with result "+printarray(array));

    }

    public static void main (String param[]) throws Exception {
        input in = new input();
        output out = new output();

	random gen = new random(1,10);

	out.write("Enter length: ");
	int length = in.readint(); 

        int array[] = new int[length];
	for (int i=0; i<length; i++) array[i] = gen.readint();

	out.writeln(printarray(array));

	quicksort(array,0,length-1);

	out.writeln("Result is: "+printarray(array));


        in.close(); out.close();
    }
}