原题链接：acwing787.归并排序
归并排序和快速排序类似，都是基于分治的，步骤如下：
（1）确定待排序数组的分界点mid, 一般取mid为待排序数组的中位数 mid = l + r >> 1;
（2）递归排序分界点的左右两侧区间，直到区间大小为1；
（3）归并两个排好序的区间，把两个有序的数组合二为一，最后合并好的数组就是排好序的数组。
归并的方法是双指针。
左右区间排好序的数组分别为left和right，我们开一个额外的，大小与原数组大小相等的数组tmp记录最后排好序的结果。
用两个指针i和j分别指向left和right的开头，指向的数就是两个数组中的最小值，把这两个值进行比较，较小的那个数就是所有数的最小值，
把这个最小值加入到tmp数组中，然后对应的指针向后移动一位，指向数组剩下部分的数中的最小值。
重复这个步骤直到某个指针走到了终点，此时另一个指针走到了一半，退出循环，把未走完的剩余部分加到答案数组tmp中。
如果两个指针指向的数相同，我们把第一个数放到tmp数组中，所以归并排序之后相同数字的相对顺序与原数组中的相对顺序相同，因此归并排序是稳定的。
时间复杂度分析：归并排序每次把当前当前数组划分为两个长度为一半的子数组，并进行排序，直到划分的数组大小为1.
比如原数组大小为n，第一次划分为两个大小为n/2的子数组进行排序，第二次划分出4个大小为n/4，。。。。这样，一共要划分n次。
每一次都要对n个数进行排序，所以每次归并都是O(n)的一个复杂度。
所以归并排序总的时间复杂度是O(nlogn)。
代码如下：
#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int q[N], tmp[N];
void merge_sort(int q[], int l, int r) {
if(l >= r) { //如果数组中没有数，或者只有一个数，直接return
return ;
}
int mid = l + r >> 1;
merge_sort(q, l, mid); //递归归并左右两部分
merge_sort(q, mid + 1, r);
int k = 0, i = l, j = mid + 1; //k记录当前tmp数组中已经放好位置的是第几个数
while(i <= mid && j <= r) {
if(q[i] <= q[j]) { //把较小的那个数放入tmp数组中
tmp[k++] = q[i++];
} else {
tmp[k++] = q[j++];
}
}
while(i <= mid) { //如果某个指针走到了尽头，则把另一个数组剩下的部分全部加入到tmp数组中
tmp[k++] = q[i++];
}
while(j <= r) {
tmp[k++] = q[j++];
}
for(int i = l, j = 0; i <= r; ++i, ++j) { //再把tmp数组的数写回到q[l~r]
q[i] = tmp[j];
}
}
int main() {
int n;
scanf("%d", &n);
for(int i = 0; i < n; ++i) {
scanf("%d", &q[i]);
}
merge_sort(q, 0, n - 1);
for(int i = 0; i < n; ++i) {
printf("%d ", q[i]);
}
return 0;
}