// destructive quicksort, polymorphic version

import java.util.*;

public class qsort<T extends Comparable<T>>
{
    public T[] A;  // array to be passed in
    public qsort(T[] b) { A=b;  }

    // find index of pivot from A[start] to A[end-1], -1 if not found
    private int pivoti(int start, int end)
    {
	int i = start;
	int piv = -1;
	while (i<end-1 && piv==-1)
	    {
		if (A[i].compareTo(A[i+1])>0) piv = i+1;
		i++;
	    }
	return piv;
    }//pivoti

    // destructive partition via swaps, returns 1st index of 2nd partition
    private int partition(int start, int end, T pivot)
    {
	int i = start; // traversal over partition
	int j = start; // index of next available slot for first partition
	while (i<end)
	    {
		if (A[i].compareTo(pivot)<=0) // swap to first partition
		    {
			T temp = A[i];
			A[i] = A[j];
			A[j] = temp;
			j++; // index next available slot
		    }
		i++;
	    }
	return j; // works because pivot ensures partitions non-empty.
    }//partition


    private void quick(int start, int end)
    {
	int piv = pivoti(start,end);
	if (piv>=0)
	    {
		int spi = partition(start,end,A[piv]);
		quick(start,spi);
		quick(spi,end);
	    }
    }
    public void quicksort() { quick(0,A.length); }


    public void print(String format)
    {
	for(T x:A) System.out.printf(format,x); 
	System.out.println();
    }

    /* main for testing
    public static void main(String[] args)
    {
	int n = Integer.parseInt(args[0]);
	Double[] M = new Double[n];
	for(int i=0;i<n;i++)
	    M[i] = (Math.random()*n*n);
	qsort<Double> QS = new qsort<Double>(M);
	QS.print("%.2f ");
	QS.quicksort();
	QS.print("%.2f ");
    }
    */
}//qsort