import java.lang.reflect.Array;
import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args)
    {
        int[] ary = new int[]{40,3,59, -1, -999,4,6,99,888,7};
//        int[] ary = new int[]{40};
//        int[] ary = new int[]{40,-999};
//        int[] ary = new int[]{40,-999,88};
        myQuickSort(ary, 0, ary.length-1);
        System.out.println("hey");
    }

    static void myQuickSort(int[] ary, int startIndex, int endIndex){
        // if the range of the sub-ary is empty or only has one element, there is no need to sort at all
        if (startIndex >= endIndex) {
            return;
        }

        // do the sorting
        Integer pivotIndex = myQuickSortHelper(ary, startIndex, endIndex);

        // divide the arrays into two sub-arrays and use the same sorting algorithm again
        myQuickSort(ary, pivotIndex+1, endIndex); // right side
        myQuickSort(ary, startIndex, pivotIndex-1); // left side
    }

    static Integer myQuickSortHelper(int[] ary, int startIndex, int endIndex){

        // the initial last smaller value index for this round
        int lastSmallerValueIndex = startIndex - 1;

        // execute the logic of quick sort
        int pivotVal = ary[endIndex]; // we pick the last element of the current range of sub-array as our pivot value
        for (int i = startIndex; i < endIndex; i++){
            int nowVal = ary[i];
            if (nowVal <= pivotVal) { // we found there is one number that is lower than the pivotValue, so we simply put it the the left side of the array
                lastSmallerValueIndex++;
                swapValInAray(ary, lastSmallerValueIndex, i);
            }
        }

        // put pivotValue to the pivotIndex
        int pivotIndex = lastSmallerValueIndex + 1;
        swapValInAray(ary, pivotIndex, endIndex);
        return pivotIndex; // this is the index that is set to have the current pivotVal forever
    }

    private static void swapValInAray(int[] ary, int i, int j){
        int tmp = ary[i];
        ary[i] = ary[j];
        ary[j] = tmp;
    }

}