Merge Sort

用于Java中Arrays.sort(Object)

优化：如果在Tiny Subarray 情况下也用merge sort的话就会太复杂，因此在size < k值的时候用insertion sort

Tips：Two pointers 的很常规的写法，但是如果要用for循环写的话，code的整个结构要差，而且要考虑corner case的时候比较复杂。很多处理two pointers的时候，用while()来限制两个pointer，而不是index本身，最后再处理index. 这一点在list里面也有体现。

Template:

1. Merge Sort
   这里的temp数组int[] temp = new int[A.length]是用来作为auxiliary，从而帮助merge two part of array, 因此空间复杂度为O(N)

   Recursion

   private void mergeSort(int[] A, int start, int end, int[] temp) {
     if (start >= end) return;
   
     int left = start, right = end;
     int mid = (start + end) / 2;
   
     mergeSort(A, start, mid, temp);
     mergeSort(A, mid+1, end, temp);
     merge(A, start, mid, end, temp);
   }
   

   Iterative(bottom-up)

   public void MergeSort(int[] nums) {
     int len = nums.length;
     for (int i = 1; i < len; i += i) {
         for (int j = 0; j < len - i; j += i+i) {
             merge(nums, j, j + len - 1, Math.min(j + len + len - 1, len - 1), temp);
         }
     }
   }
   

2. Merge Two part of an Array
   Version 1:

   private void merge (int[] nums, int start, int mid, int end, int[] temp) {
    int left = start, right = mid + 1, index = start;
   
    // merge two sorted subarrays in nums to temp
    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 nums
    for (index = start; index <= end; index++) {
        nums[index] = temp[index];
    }
   }
   

   Version 2:

   private static void merge(int[] a, int[] temp, int lo, int mid, int hi) {
     int i = lo, j = mid+1;
   
     for (int k = lo; k <= hi; k++) {
       if (i > mid) aux[k] = a[j++];
       else if (j > hi) aux[k] = a[i++];
       else if (less(a[j], a[i])) aux[k] = a[j++];
       else aux[k] = a[i++];
     }
   }