package weblab;
class Solution
{
    /**
     * @param array of integers to be sorted.
     */
    public static void quickSort(int[] elements){

        // Base Case
        if(elements.length < 2) {
            return;
        }
        // Checks when there are only 2 elements left whether they need to be reversed.
        if(elements.length == 2) {
            if(elements[0] > elements [1]) {
                int temp = elements[0];
                elements[0] = elements[1];
                elements[1] = temp;
            }
            return;
        }

        // initializes new arrays and counters.
        int comp = elements[elements.length - 1];
        int[] small = new int[elements.length];
        int[] large = new int[elements.length];
        int smallCount = 0;
        int largeCount = 0;

        // checks whether numbers in the original array are higher or lower then comp,
        // then puts them into the right array
        for(int i = 0; i < elements.length - 1; i++) {

            if(elements[i] < comp) {
                small[smallCount] = elements[i];
                smallCount++;

            } else {
                large[largeCount] = elements[i];
                largeCount++;
            }
        }

        //recreates the arrays made above, this time with the right length
        int[] smaller = new int[smallCount];
        for(int i = 0; i < smallCount; i++) {
            smaller[i] = small[i];
        }
        int[] larger = new int[largeCount];
        for(int i = 0; i < largeCount; i++) {
            larger[i] = large[i];
        }
        //recursion call for both made arrays.
        quickSort(smaller);
        quickSort(larger);

        //puts the now sorted arrays back together in a single array.
        for(int j = 0; j < smallCount; j++) {
            elements[j] = smaller[j];
        }
        elements[smallCount] = comp;
        int m = 0;
        for(int k = smallCount + 1; k < smallCount + largeCount + 1; k++) {
            elements[k] = larger[m];
            m++;
        }
    }
}
//