Merge Sort Algorithm:

Problem Description
Given an array arr , its starting position l and its ending position r . Sort the array using merge sort algorithm.

Example 1:

Input: arr = [4, 1, 3, 9, 7], l = 0, r = 4 
Output: [1, 3, 4, 7, 9]
Explanation: 

Example 2:

Input: arr = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1], l = 0, r = 9 
Output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Explanation: 

Constraints:
1 <= N <=$10^5$
1 <= arr[i] <= $10^5$

class Solution {
    public int[] sortArray(int[] nums, int start, int end) {
        mergeSort(nums, start, end);
        return nums;
    }
    //merge sort algorithm
    private void mergeSort(int [] nums, int start, int end) {
        //base case
        if(start >= end)
            return; 
        //find mid and divide array at mid element
        int mid = (start+end)/2; 
        mergeSort(nums, start, mid);
        mergeSort(nums, mid+1, end);
       mergeSortedArrays(nums, start, end, mid); 
       
    }
    private void  mergeSortedArrays(int [] nums, int start, int end, int mid) {
        //create two arrays considering mid as partition point
        int n = mid-start+1;
        int m = end-mid; 
        int left [] = new int[n]; 
        int right [] = new int [m];
        for(int i=0; i<n; i++)
            left[i] = nums[start+i]; 
        for(int i=0; i<m; i++) 
            right[i] = nums[mid+i+1]; 
        //copy elements in left & right array
        // System.arraycopy(nums , start+0, left, 0, n); 
        // System.arraycopy(nums, mid+1, right,0, m); 
        
        int i = 0;
        int j = 0;
        int k = start;
        
        while(i<n && j<m) {
            if(left[i] < right[j]) {
                nums[k] = left[i]; 
                i++;
                k++;
            }
            else {
                nums[k] = right[j]; 
                j++; 
                k++;
            }
        }
        //left is having few more elements left
        while(i<n) {
            nums[k] = left[i]; 
            i++;
            k++;
        }
        //right is having few more elements left
        while(j<m) {
            nums[k] = right[j]; 
            j++;
            k++;
        }
    }
}