class scell  // sorted
{
    public double head;
    public scell tail;
    public scell(double h, scell t) {head=h;  tail=t;}
    public static scell randomize(int n) // return random list of length n
    {
	if (n==0) return null;
	else return (new scell(Math.random(), randomize(n-1)));
    }    

    // append attaches one list to the end of "this" list (oop style)
    public void append(scell B)
    {
	scell i = this;
	while (i.tail !=null) i=i.tail;
	i.tail = B;
    }

    // find pivot, return pointer to pivot cell, null if no pivot
    public static scell findpivot(scell A)
    {
	scell p = null;
	while (A!=null && A.tail!=null && p==null)
	    {
		if (A.head > A.tail.head) p = A.tail;
		A=A.tail;
	    }
	return p;
    }

    // partition constructs two new lists
    public static parts partition(scell A, double pivot)
    {
        scell L = null;
	scell R = null;
	while (A!=null)
	    {
		if (A.head<=pivot) L = new scell(A.head,L);
		else R = new scell(A.head,R);
		A=A.tail;
	    }
	return new parts(L,R);
    } // partition

    // main quicksort procedure (must be constructive/static)
    public static scell qsort(scell A)
    {
	scell pivcell = findpivot(A);
	if (pivcell == null) return A;  // nothing to do if no pivot
	else 
	    {
		parts Ps = partition(A,pivcell.head);
		scell L = qsort(Ps.Left);
		scell R = qsort(Ps.Right);
		L.append(R);
		return L;
	    }
    } //qsort


    //tostring method for printing
    public String toString()
    {
	if (tail==null) return head+""; 
	else return head+" "+tail.toString();
    }

} // scell


// class that encapsulates two lists (returned by partition)
class parts
{
    public scell Left;
    public scell Right;
    public parts(scell l, scell r) {Left=l;  Right=r;}
}


public class quicksortnew
{
    public static void main(String[] args)
    {
	int n = Integer.parseInt(args[0]);
	scell A = scell.randomize(n);
	System.out.println(A);
	A = scell.qsort(A);
	System.out.println("\nSorted: "+A);	
    }
}