归并排序最核心的思想就是 merge 两个有序的数组。假设两个只有一个元素的数组合并，比如 [34], [33]，合并之后就是 [33, 34]。假设这个数组要和 [1, 100] 合并，合并之后就是 [1, 33, 34, 100]。

可以看出当大小为 n 的有序数组和大小为 m 的有序数组合并之后大小就是 n + m。所以最重要的就是写出高效的合并算法，假设函数的签名是 

1
2
3
// a， b 需要合并的数组
// temp 用来存放合并后的数组
void merge (int[] a, int[] b, int[] temp)

其中 a，b 可以用同一个数组中的 low，mid，high 三组下标表示，这样做的原因是为了尽量减少内存开销。

1
2
3
4
5
6
7
8
9
10
11
12
// arr 原数组
// low, mid, high 分割成两个需要 merge 的子数组
void merge (int[] arr, int low, int mid, int high, int[] temp)  {
    int i = low, j = mid + 1, k = 0;
    while (i <= mid && j <= high) {
      if (arr[i] <= arr[j]) tmp[k++] = arr[i++];
      else tmp[k++] = arr[j++];
    }
    while (i <= mid) tmp[k++] = arr[i++];
    while (j <= high) tmp[k++] = arr[j++];
    System.arraycopy(tmp, 0, arr, low, k);
}

在 merge 函数已经完成的情况下，接下来就需要把原来的数组进行递归地拆分然后 merge。

1
2
3
4
5
6
7
8
void mergeSort(int[] arr, int low, int high, int[] tmp) {
   if (low < high) {
     int mid = low + (high - low) / 2;
     mergeSort(arr, low, mid, tmp);
     mergeSort(arr, mid + 1, high, tmp);
     merge(arr, low, mid, high, tmp);
   }
}