• 步骤：
  • make a tmp array to store sorted result
  • divide and conquer, partition by middle element
  • merge: iterate left and right array, compare and store in tmp array
  • copy tmp array to original array

public void mergeSort(int[] array) {

    int[] tmp = new int[array.length];
    recMergeSort(tmp, 0, array.length - 1, tmp);
}

public void recMergeSort(int[] array, int left, int right, int[] tmp) {
    // 至少两个元素
    if (left >= right) return;

    int mid = left + (right - left) / 2;

    recMergeSort(array, left, mid, tmp);
    recMergeSort(array, mid + 1, right, tmp);

    merge(array, left, mid, right, tmp);
}

private void merge(int[] array, int left, int mid, int right, int[] tmp) {

    int i = left;
    int j = mid + 1;
    int index = left;

    while (i <= mid && j<= right) {
        if (array[i] < array[j]) {
            tmp[index++] = array[i++];
        } else {
            tmp[index++] = array[j++];
        }    
    }

    while (i <= mid) {
        tmp[index++] = array[i++];
    }

    while (j <= right) {
        tmp[index++] = array[j++];
    }

    for (index = left; index <= end; index++) {
        array[index] = tmp[index];
    }
}