QuickSortRecurse.java

class Solution 
{
    public int[] sortArray(int[] nums) 
    {
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }
    
    public void quickSort(int[] nums, int left, int right)
    {
        /* right = left
         * This means you have recursed to base levels
         * left and right represent indexes here.
         * Basically we are making sure that the recursion happens until size of array is one.
        */
        if(right >= left)
        {   
            /* STEP - 1: Partitioning
             * Partition function has two main goals.
             * 1. Find the position of a pivot.
             * 2. Modify nums array such that all elements less than pivot
             * are arranged to left and greater to the right.
             * So after partitioning we can exclude the pivot and select a new pivot.
            */
            // It is good to select a random pivot. (This is a snippet for generating random numbers between left and right inclusive).
            Random r = new Random();
            int myRandomNumber = 0;
            myRandomNumber = r.nextInt(right-left+1)+left;
            
            // Here I am moving the random number to the left most part of the array, so that I 
            // can select it as my pivot.
            int temp = nums[left];
            nums[left] = nums[myRandomNumber];
            nums[myRandomNumber] = temp;
            int pivotPosition = partition(nums, left, right);
            
            //Quick sort left
            // It is important to understand that pivot is already in its correct position. So need need to include it.
            quickSort(nums, left, pivotPosition - 1);
            
            //Quick sort right
            quickSort(nums, pivotPosition + 1, right);           
        }
    }
    
    public int partition(int[] nums, int left, int right)
    {   
        // x is my pivot
        int x = nums[left];
        int i = left;
        // i represents the pointer for boundary.
        // j is simply for iteration.
        for(int j = left + 1; j <= right; j++)
        {
            if(nums[j] <= x)
            {
                i++;
                int temp = nums[j];
                nums[j] = nums[i];
                nums[i] = temp;
            }
        }
        int temp = nums[i];
        nums[i] = nums[left];
        nums[left] = temp;
        return i;
    }
}