July 31, 2019

Merge Sort

经典 Divide and Conquer 算法。
Time complexity: O(n log(n)) - 每层合并 (merge) 需要 O(n), 有 logn 层
Space complexity: O(n) - 递归 (mergeSort) 压栈 O(n/2 + n/4 + n/8 + .. + 1) = O(n)
分析

public class Solution {
  public int[] mergeSort(int[] array) {
    if (array == null || array.length == 0) {
      return array;
    }
    // allocate helper array: guarantee no more than 0(n) space is used
    int[] helper = new int[array.length];
    mergeSort(array, helper, 0, array.length - 1);
    return array;
  }

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

  private void merge(int[] array, int[] helper, int left, int mid, int right) {     
    for (int i = left; i <= right; i++) {
      helper[i] = array[i];
    }
    int index = left;
    int i = left;
    int j = mid + 1;
    while (i <= mid && j <= right) {
      if (helper[i] <= helper[j]) {
        array[index++] = helper[i++];
      } else {
        array[index++] = helper[j++];
      }
    }
    while (i <= mid) {
      array[index++] = helper[i++];
    }
    while (j <= right) {
      array[index++] = helper[j++];
    }
  }
}