Merge Sort 重點在 split(拆分) 跟 merge

1. 一開始要記得 create temp array，方便之後存 merge 後的部份 array。

2. merge 完要把 temp 裡的值 update 回原 array 裡

   public int msort(int[] nums) {

    int[] temp = new int[nums.length];
    mergeSort(nums, 0, nums.length - 1, temp);
   

   }

   private void mergeSort(int[] nums, int start, int end, int[] temp) {

    if (start >= end) {
        return;
    }
   
    mergeSort(nums, start, (start + end) / 2, temp);
    mergeSort(nums, (start + end) / 2 + 1, end, temp);
    merge(nums, start, (start + end) / 2, end, temp);
   

   } private void merge(int[] nums, int start ,int mid, int end, int[] temp) {

    int index = start, left = start, right = mid + 1;
    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 array to nums
    for (int i = start; i <= end; i++) {
        nums[i] = temp[i];
    }
   

   }