import java.util.List;
import java.util.Collections;
import java.util.ArrayList;
public class Q
{
    public static void main(String[] args)
    {

        ArrayList<Integer> x = new ArrayList<>();
        for(int k = 0; k < 1000000; k++)
        {
            x.add(k);
        }
        Collections.shuffle(x);
        /*x.add(1);
        x.add(2);
        x.add(8);
        x.add(4);
        x.add(7);
        x.add(0);
        x.add(3);
        x.add(-1);
        x.add(0);*/
        System.out.println(x);
        quickSort(x, 0, x.size());
        System.out.println(x);
    }

    private static <T extends Comparable<T>> void swap(ArrayList<T> x, int k, int l)
    {
        T tmp = x.get(k);
        x.set(k, x.get(l));
        x.set(l, tmp);
    }

	private static <T extends Comparable<T>> int pivot(ArrayList<T> x, 
		int start, int end)
    {
        int p = start;
        int q = end;   //this is the INDEX of the last entry
        while(p < q - 1)
        {
            if(x.get(p).compareTo(x.get(p + 1)) > 0)
            { 
                swap(x, p, p + 1);
                p++;
            }
            else if(x.get(p).compareTo(x.get(p + 1)) < 0)
            {
                swap(x, p + 1, q - 1);
                q--;
            }
            else
            {
                p++;
            }
        }
        return p;
    }
    public static <T extends Comparable<T>> void quickSort(ArrayList<T> x, int start, int end)
    {   
        if(start < end - 1)
        {
        int n = pivot(x, start, end);
            quickSort(x, start, n + 1 );
            quickSort(x, n + 1, end);
        }
    }
}