MergeSortRecursive.java

class Solution 
{
    public int[] sortArray(int[] nums) 
    {
        mergeSort(nums, nums.length);
        return nums;
    }
    
    public void mergeSort(int[] nums, int length)
    {
        // That is if the array is one single size return;
        // This is the base case.
        if(length < 2)
            return;
        
        // Divide the length/2 to find mid point.
        int mid = length/2;
        
        /* Mid Point:
         * For example, if the array is [5, 4, 9, 8, 2]
         * length = 5; length/2 would give mid = 2. Mid represents size not index.
         * This means, 2 is the size of the left subarray and
         * (length - mid) i.e (5 - 2 = 3) is the size of right sub array. 
         * So, left-subarray = [5, 4]; right-subarray is [9, 8, 2]
        */
        // Array for holding the left integers.
        int[] left = new int[mid];

        // Array for holding the right integers.
        int[] right = new int[length - mid];
        
        // In this part we are simple iterating over the main array and creating left and right sub arrays.
        for(int i = 0; i < length; i++)
        {
            if(i < mid)
            {
                left[i] = nums[i];
            }
            else
            {
                right[i - mid] = nums[i];
            }
        }

        /* BEAUTY OF RECURSION
        * Now we simply call the same function mergeSort on left subarray and right subarray.
        * Left sub array: [5, 4] after the below recursion would become two new sub arrays [5] and [4]. 
        * (Yay we have reached out base case)
        * Right sub array: [9, 8, 2] after the below recursion would become [9] and [8, 2].
        * [8, 2] will further recurse to form [8] and [2].
        */
        mergeSort(left, mid);
        mergeSort(right, length - mid);
        
        /* Once we reach base cases we merge by comparing them against each other.
        * For example [5] and [4] would me merged into [4, 5]
        * [8] and [2] will be merged into [2, 8]
        * [4, 5] and [2, 8] will be merged into [2, 4, 5, 8]
        */
        merge(nums, left, right, mid, length - mid);  
    }
    
    /* Merge logic is quite simple
    * If you have two arrays say A[4, 5] and B[2, 8] coming from [5, 4, 8, 2]. It is imporant to note than both [4, 5] and 
    * [2, 8] come sorted as a consequence of the previous merge call to base arrays [5], [4] & [8], [2] separately.
    * Now assuming A and B are sorted. 
    * We will compare this way:
    * 1. is 4 < 2, no? so keep 2 in the first index of [4, 5, 2, 8] makingit [2, 5, 2, 8] and increment pointer in B to 8.
    * 2. is 4 < 8 yes? so keep 4 in the second index of [2, 5, 2, 8] making it [2, 4, 2, 8] and incrment pointer in A to 5.
    * 3. is 5 <8 yes? so keep 5 in third index of [2, 5, 2, 8] making it. [2, 4, 5, 8].
    * There you go it is sorted now.
    */
    public void merge(int[] nums, int[] left, int[] right, int l, int r)
    {
         int i = 0; int j = 0; int k = 0;
         while(i < l && j < r)
         {
             if(left[i] <= right[j])
             {
                 nums[k++] = left[i++];
             }
             else
             {
                 nums[k++] = right[j++];
             }
         }
        
        while(i < l)
        {
           nums[k++] = left[i++]; 
        }
        while(j < r)
        {
           nums[k++] = right[j++]; 
        }
    }
}