模板

  1. static final int N = 1000010;
  2. static int[] q = new int[N];
  3. static int[] tmp = new int[N];
  4. void merge_sort(int q[], int l, int r) {
  5.     if (l >= r) return;
  7.     int mid = l + r >> 1;
  8.     merge_sort(q, l, mid);
  9.     merge_sort(q, mid + 1, r);
  11.     int k = 0, i = l, j = mid + 1;
  12.     while (i <= mid && j <= r) {
  13.         if (q[i] <= q[j]) tmp[k ++] = q[i ++];
  14.         else tmp[k ++] = q[j ++];
  15.     }
  16.     while (i <= mid) tmp[k ++] = q[i ++];
  17.     while (j <= r) tmp[k ++] = q[j ++];
  18.     // 这个for循环是将tmp中的值重新赋值给q
  19.     // 因为是在递归中，所以并不是无用的，如果删除答案会错误
  20.     for (int m = l, n = 0; m <= r; m++,n++) {
  21.         q[m] = tmp[n];
  22.     }
  23. }

思想

  1. 将数组平均分成两部分（奇数个数的话就是一个为n/2个，一个为n/2+1个）。
  2. 分别递归地排序数组的这两部分。
  3. 将排好序的两部分归并成一整块。
    方法：重新开辟一个数组空间（tmp），利用双指针的移动，将两部分中更小（或更大）的那个数存到tmp中，再将tmp的值存入q中。
  4. 时间复杂度为O(nlogn)。

与快排的区别

相同点

都是分治思想

不同点

1. 分界点

快排：随机一个值

归并：数组中间值 （l + r）/2 或者 l + r >> 1

2.最难点

快排：把一个数组划分成两端

归并：把两个有序序列合二为一

合并时用双指针的思想，都指向最小值，然后进行两个指针指向数字的比较，从而进行排序

3. 空间使用

归并排序要使用一个额外的数组帮助合并