import java.util.Random;

public class QuickSorterO {
    public static Random RAND = new Random();
    public static void swap(Comparable[] array,int i1,int i2) {
        var tmp = array[i1];
        array[i1] = array[i2];
        array[i2] = tmp;
    }
    // Q(2 n) = n + 2 Q(n)
    // O(n log n)
    public static void sort(Comparable[] array) {
        sort(array,0,array.length);
    }
    // 3 8 2 9 4 7 6 3
    // 3 2 4 3<6>8 7 9
    // 3 2 3<4> | 7<8>9
    // <2> 3 3 | 4 | 7 <8> 9
    /*
     * cmp is either 0 or 1
     * if cmp=0, then the comparison is less than (<)
     * if cmp=1, then the comparison is less than or equal to (<=)
     */
    public static int partition(Comparable[] array,int start,int end,Comparable pivot_val,int cmp) {
        int i1=start, i2=end;
        while(i1 < i2) {
            // a.compareTo(b) = 0 when a and b are equal
            //                = negative when a is less than b
            //                = positive when a is greater than b
            int cmpval1 = array[i1].compareTo(pivot_val);
            int cmpval2 = array[i2-1].compareTo(pivot_val);
            if(cmpval1 < cmp) i1++;
            else if(cmpval2 >= cmp) i2--;
            else if(cmpval1 >= cmp && cmpval2 < cmp) swap(array, i1, i2-1);
            else assert false; // Shouldn't get here
        }
        return i1;
    }
    public static void sort(Comparable[] array,int start,int end) {
        int n = end - start;
        if(n < 2)
            return;
        int pivot = RAND.nextInt(n)+start;
        Comparable pivot_val = array[pivot];

        int i1 = partition(array, start, end, pivot_val, 0);
        int i2 = partition(array, i1, end, pivot_val, 1);
        
        // sort everything not equal to the pivot
        sort(array,start,i1);
        sort(array,i2,end);
    }

    public static void main(String[] args) {
        Integer[] testVals = new Integer[200];
        for(int i=0;i<testVals.length;i++)
            testVals[i] = RAND.nextInt();
        QuickSorterO.sort(testVals);
        for(int i=1;i<testVals.length;i++)
            assert testVals[i-1] <= testVals[i];
        var array = new Integer[]{3,5,2,7,100,4};
        QuickSorterO.sort(array);
        for(int i=0;i<array.length;i++)
            System.out.println(array[i]);
        var array2 = new String[]{"fish","ant","rice","people","bug","ham"};
        QuickSorterO.sort(array2);
        for(int i=0;i<array2.length;i++)
            System.out.println(array2[i]);
    }
} // T(N) = k*N + 2*T(N/2) -> O(N*Log(N))