在学习归并排序之前，个人认为需要掌握双指针的相关知识（快慢指针，左右指针之类的）。
归并排序是一种运用快慢指针与递归来实现的算法
思路
拆分过程-“归”的过程
对于数组：
5 4 3 2 1
我们先把其分为两部分：
5 4 和 3 2 1 //两个都可以，看你选择
5 4 3 和 2 1 //两个都可以，看你选择
然后再对于左右两部分再次拆分，直到分成一个元素
而这个过程，我们可以运用递归来进行数组的拆分
f(0 , 4)->f(0 , 2) + f(3 , 4)->f(0 , 1) + f(2 , 2) + f(3 , 3) + f(4, 4) //返回的是边界下标
而我们就可以利用这个过程将大数组转换成小数组，最终得到一个有序的数组
排序过程-“并”的过程
我们取递归返回的其中一个过程为例：
3 4 5 和 1 2
我们定义一个临时变量来存储部分排序好的元素，假设这个变量为temp
我们先比较 3 和 1，发现 1 比较小
于是我们把 1 放入temp
继续比较 3 和 2 ， 发现 2 比较小
于是我们把 2 放入temp
这个时候右数组到头了，于是我们停止比较，并且把左数组剩下的元素全放到temp里面去
于是我们得到的temp就是
1 2 3 4 5
然后我们将temp赋值给原数组，把原数组覆盖掉
我们明显可以发现，和原来相比较，原数组更加有序了（已经有序了，我们取的是排序的最后一步）
代码实现
#include<iostream> using namespace std; const int N = 1e5; int arr[N]; int temp[N]; //辅助数组 void merge_sort(int l , int r){ //递归实现归并排序 if(l >= r) return; //只有一个元素或者没有，自然有序，不用管 int m = (l + r) / 2; //这里就是把数组拆开 merge_sort(l , m); //处理左边 merge_sort(m + 1 , r); //处理右边 int i = l , j = m + 1 , k = 0; //i和j分别代表左右数组的左边界起点 k是临时变量，作为temp数组的边界 while(i <= m && j <= r){ if(arr[i] > arr[j]){ temp[k] = arr[j]; //把小的数放进来 k++; j++; }else{ temp[k++] = arr[i++]; } } //接下来判断i和j哪个没走完，把剩下的元素放进去 while(i <= m) temp[k++] = arr[i++]; while(j <= r) temp[k++] = arr[j++]; //然后把temp覆盖arr，即把temp重新赋值给arr,arr的起始位置是l和r，temp的起始位置是0 for(i = l , k = 0 ; i <= r ; i++ , k++){ arr[i] = temp[k]; } } int main(){ int n; cin >> n; for(int i = 0 ; i < n ; i++){ cin >> arr[i]; } merge_sort(0 , n - 1); //将左边界和右边界传入 for(int i = 0 ; i < n ; i++){ cout << arr[i] << ' '; } cout << endl; return 0; }总结
归并排序的整体难度起始不大，然后复杂度和稳定性这两个方面的话，我不清楚这个复杂度是怎么算出来的，但是我查出来是O()。归并排序不是一个稳定的算法，因为临时数组会反复地把原数组进行覆盖。
