Note:

先分到不可分，再merge起来

Step 1: recursion来完成divided

base case: left == right

recursion rule：找中点，并且从中点对半劈开

Step 2: merge two array

谁小移谁，参考merge two sorted linked list

Key word:

public class Solution {
  public int[] mergeSort(int[] array) {
    if (array == null || array.length <= 1) {
      return array;
    }
    return mergeSort(array, 0, array.length - 1);
  }

  private int[] mergeSort(int[] array, int left, int right) {
    if (left == right) {
      return new int[]{array[left]};
    }
    int mid = left + (right - left) / 2;
    int[] leftResult = mergeSort(array, left, mid);
    int[] rightResult = mergeSort(array, mid + 1, right);
    return merge(leftResult, rightResult);
  }

  private int[] merge(int[] one, int[] two) {
    int[] result = new int[one.length + two.length];
    int first = 0;
    int second = 0;
    int cur = 0;
    while (first < one.length && second < two.length) {
      if (one[first] <= two[second]) {
        result[cur++] = one[first++];
      } else {
        result[cur++] = two[second++];
      }
    }
    while (first < one.length) {
      result[cur++] = one[first++];
    }
    while (second < two.length) {
      result[cur++] = two[second++];
    }
    return result;
  }
}

Complexity Analysis:

TC: O(N* logN); divide: O(N) + merge: O(N* LogN)

SC:O(N); call stack: logN, heap: n + n / 2 + n / 4 +… + 1 = O(N);