Merge Sort

/*
 本算法答案由上岸科技提供。
 上岸科技是一个专致力于高效培养北美留学生拥有实际面试能力的团体。
 我们采用小班化线上，线下教学让学生更快，更好的学习到想要的知识。
 团队主要由一群怀揣情怀于美国高校毕业的一线IT公司工程师构成。
 我们坚信对于求职者算法并不是全部，合理的技巧加上适当的算法培训能够大大的提升求职成功概率也能大大减少刷题的痛苦。
 正如我们的信仰：我们教的是如何上岸而不仅是算法。
 更多信息请关注官网：https://www.shanganonline.com/
*/
public class Solution {
    public int[] sortArray(int[] nums) {
        // use a shared temp array, the extra memory is O(n) at least
        int[] temp = new int[nums.length];
        mergeSort(nums, 0, nums.length - 1, temp);
        return nums;
    }
    
    private void mergeSort(int[] nums, int start, int end, int[] temp) {
        if (start >= end) {
            return;
        }
        
        int mid = (start + end) / 2;

        mergeSort(nums, start, mid, temp);
        mergeSort(nums, mid + 1, end, temp);
        merge(nums, start, mid, end, temp);
    }
    
    private void merge(int[] nums, int start, int mid, int end, int[] temp) {
        int left = start;
        int right = mid + 1;
        int index = start;
        
        // merge two sorted subarrays in A to temp array
        while (left <= mid && right <= end) {
            if (nums[left] < nums[right]) {
                temp[index++] = nums[left++];
            } else {
                temp[index++] = nums[right++];
            }
        }
        while (left <= mid) {
            temp[index++] = nums[left++];
        }
        while (right <= end) {
            temp[index++] = nums[right++];
        }
        
        // copy temp back to A
        for (index = start; index <= end; index++) {
            nums[index] = temp[index];
        }
    }
}