import java.util.*;

    
public class Sortieren
{

    /** Partitions a so that lower half contains elements <= x and upper half contains elements >=x. 
	@param a. The array to be partitioned (to be precise, only a[p..q] will be partitioned).
	@param p. Lower endpoint.
	@param r. Upper endpoint.
	@param c. The comparator giving the ordering.
	@return an index q such that the following hold. 
	a[p..q]<=x<=a[q+1..r]. If x occurs in a[p..r-1] then p<=q<r. 
	Precondition: p<=r. 
    */
    public static int partition(Object[] a, int p, int r, Object x, Comparator c) {
	if (p==r) {
	    if (c.compare(a[p],x) <= 0)
		{return p; }
	    else
		{return p-1;}
	}
	else if (c.compare(a[p],x) < 0) return partition(a,p+1,r,x,c);
	else if (c.compare(a[r],x) > 0) return partition(a,p,r-1,x,c);
	else {
	    Object hilf = a[p];
	    a[p] = a[r]; 
	    a[r] = hilf;
	    return partition(a, p, r-1, x, c);
	} 
    }

    /** Umarrangieren des Arrays in unteren und oberen Teil. 
	a[p..q] <= a[q+1..r]. p<=q<r. 
	Vorbedingung: p<r.
	@return Den Teilungspunkt q. 
    */
    public static int partition(Object[] a, int p, int r, Comparator c) {
	return partition(a, p, r, a[p], c);
    }

    /** Selbe Spezifikation wie partition, aber zufaellige Pivotwahl. */
    public static int randomisedpartition(
	   Object[] a, int p, int r, Comparator c, java.util.Random gen) {
	int piv = gen.nextInt(r-p+1) + p;
	Object hilf = a[p]; a[p] = a[piv]; a[piv] = hilf;
	return partition(a, p, r, c);
    }



    public static void sort(Object[] a, int p, int r, Comparator c) {
	if (p==r) ;
	else {
	    int q = partition(a, p, r, c);
	    sort(a,p,q,c);
	    sort(a,q+1,r,c);
	}
    }
}