前言
归并排序的思路其实和快速排序的很像，都有递归的过程。
但是区别是：快速排序是先处理好这一层，然后再进行传递，在传递到底后，其实排序就已经完成了。而归并排序是先直接一直传递到最底层，相当于先把区间细分好，然后在归的过程中处理数据。
所以我们说分治算法基本都是三步：
- 分成子问题
- 递归处理子问题
- 子问题合并
而实际上快速排序并没有第三步
递归中独特的就是他有第三步，而第三步的处理也不是很难。可能是因为比较认真的分析过快速排序了，感觉归并排序里面没有什么特别大的疑问
正文
动图：
这里我要专门解释一下了，上次的快速排序我直接放图但是自己没看，结果后来看发现根本理解不了它的逻辑
这个图我倒是理解了：这个图是已经分治完毕（传递完毕），第一次进行最小的一层，将两个只有一个数的区间进行合并，然后将两个分别含有两个数的区间合并，也就是1-2-4-8-16这样，最后就回归完毕了。
合并的思路也很简单，就是给两个数组各一个指针指向他们的开头，由于他们都是已经从小到大排列好的，所以我们就可以一直对两个数组中当前指针指向的数进行比较（他们分别代表剩下未处理的数中的最小值）。
现在我们来看看代码
#include<bits/stdc++.h>
using namespace std;
// 防止数组栈溢出
const int N = 1e6 + 10;
int a[N], tmp[N];
void merge_sort(int a[],int l,int r){
if(l>=r)
return;
int mid = (l + r) >> 1;
merge_sort(a, l, mid), merge_sort(a, mid + 1, r);
int k = 0, i = l, j = mid + 1;
// i和j是两个指针，这里虽然是一个数组，但是我们要将他模拟成两个数组
while(i<=mid&&j<=r)
if(a[i]<=a[j])
//k++,先使用k以后再让k+1
tmp[k++] = a[i++];
else
tmp[k++] = a[j++];
// 一般会有一个数组里有多出来的
// 因为已经排好序了，所以直接将他们全部放到数组后面
while(i<=mid)
tmp[k++] = a[i++];
while(j<=r)
tmp[k++] = a[j++];
//将临时数组赋值给正式数组，改变正式数组中的内容，这样才能回归
for (i = l, j = 0; i <= r;i++,j++) a[i] = tmp[j];
}
int main(){
int n;
scanf("%d", &n);
for (int i = 0; i < n;i++){
scanf("%d", &a[i]);
}
merge_sort(a, 0, n - 1);
for (int i = 0; i < n;i++){
printf("%d ", a[i]);
}
return 0;
}
分析
声明一下，这里面很多问题点都是和快速排序共通的，我就不进行说明了。所以建议先看完快速排序的文章点这里进入快速排序文章
分析1
归并排序的时间复杂度严格为nlogn
这里有两个值得一提
- 这里的log底数为2
- 快速排序的理想时间复杂度也是这个，但是那是它的平均时间复杂度（每次都能将数组平均分的话就是最理想的状态，而它每轮取的位置的期望值正好就是n/2，也就是取到中间），最差情况时间复杂度是n^2，我的快速排序文章里有分析
其实归并排序的时间复杂度分析和快速排序理想状态一样:第一层将数组分为两份，第二层分为四份....最后第logn次可以将数组分为n份，其中n是数组长度。也就是说现在每一份里面的数都只有一个。计算方法也很简单，我们假设需要n次，那么就是n=2^x，解方程即可。
我们进行了logn层，每一层都会把所有数据遍历一次，所以最后我们的时间复杂度就是nlogn
分析2
为什么不使用mid-1作为分界线呢
即 merge_sort(q, l, mid - 1 ), merge_sort(q, mid, r)
在快速排序中我们讲了位运算中的>>相当于除法，而这个除法是向下取整的，所以有可能会为l（比如l为1,r为2，那么mid就是1），这样就会造成无限划分
如果想要解决这个问题，可以mid=l+r+1>>1，这样就会向上取整。至于为什么我这里没有加括号，是因为位运算的优先级是比加减法要低的，所以可以不加，只不过有些编译器会提醒你这样不好。
分析3
知识点：对于自增自减的利用
老师代码中的这种用法我是第一次见，真的耳目一新，以后我也会去尝试使用这种方法
tmp[k++] = a[i++];这里就是先让这个语句中的值分别是k，i，在这条语句执行完毕后再让这两个变量各自进行一次自增。这种方法相当于把三行代码变成了一行
分析4
知识点：for循环括号中进行一些变量的改动
它的效果与分析3相同，都是一种很好的方法
结语
