import java.util.List;

public class QuickSort<T>
{
	public static <T extends Comparable<T>> void sort(List<T> list)
	{
		quicksort(list, 0, list.size());
	}
	
	
	private static <T extends Comparable<T>> void quicksort(List<T> list, int p, int r)
	{
		if (p < r)
		{
			int q = partition(list, p, r-1);
			quicksort(list, p, q-1);
			quicksort(list, q+1, r);
		}
	}
	
	
	private static <T extends Comparable<T>> int partition(List<T> list, int p, int r)
	{
		T tempi;
		T x = list.get(r);
		int i = p-1;
		for (int j=p; j <= r-1; ++j)
		{
			if (list.get(j).compareTo(x) <= 0)
			{
				++i;
				tempi = list.get(i); //swap A[i] <-> A[j]
				list.set(i, list.get(j));
				list.set(j, tempi);
			}
		}
		tempi = list.get(i+1); //swap A[i+1] <-> A[r]
		list.set(i+1, list.get(r));
		list.set(r, tempi);
		
		return i+1;
	}
}