思想
主要就是将两个有序数组合并成一个有序数组 第一步： 将数组分解，当分解成单个元素为一组的时候就说明这个数组是有序的 第二步： 将两两有序数组进行合并，将两个有序数组合并成一个有序数组。重复第二步，直至排序完成 合并的步骤(Merge函数)：先申请两数组合并后大小的空间，然后将两个排好序的数组逐一进行比较，往申请的空间里放
详细流程
该部分内容来源：https://blog.csdn.net/qq_35344198/article/details/106857042
这是一个无序数列：4、5、8、1、7、2、6、3，我们要将它按从小到大排序。按照归并排序的思想，我们要把序列逐层进行拆分
序列逐层拆分如下
然后从下往上逐层合并，首先对第一层序列1（只包含元素4）和序列2（只包含元素5）进行合并
创建一个大序列，序列长度为两个小序列长度之和，p1、p2指针分别指向两个小序列的第一个元素，p指向大序列的第一个元素
比较p1、p2指向的元素，4小于5，将4填入p指向的元素，p、p1往右移一位
此时，序列1已经没有元素，将序列2的元素依次填入大序列中
序列8和1，序列7和2，序列6和3，用同样的方式填入新的序列
接着，以4、5为序列1，1、8为序列2，继续进行合并
创建一个序列长度为4的大序列，p1指向序列1的第一个元素4，p2指向序列2的第一个元素1，p指向大序列的第一个元素
4和1比较，4大于1，1填入p指向的元素，p、p2往右移一位
4和8比较，4小于8，4填入p指向的元素，p、p1往右移一位
5和8比较，5小于8，5填入p指向的元素，p、p1往右移一位
自此，序列1已经没有元素，将序列2的元素依次填入大序列中
序列2、7和序列3、6以同样的方式合并成新的序列
最后，将序列1、4、5、8和序列2、3、6、7以同样的方式继续合并成新的序列
至此所有的元素都是有序的
重难点
递归部分
递归的步骤顺序大致如下图：
数组初始化
代码中使用的是初始化成L-R+1个0的数组，这种初始化对应的是v[index++]=n1[i++]，数组要有初值0，不然报错 还可以用另一种方法向数组中放入值，Push_back()直接往数组中放元素，不用给数组赋初值为0
C++代码：
#include<stdio.h>#include<iostream>#include<vector>using namespace std;
void Merge(vector<int> &vec, int L, int mid, int R) { int i = L, j = mid + 1, index = 0; //创建一个临时数组，内容为R-L+1个0 vector<int> tmp(R - L + 1);//意为tmp中有R-L+1个0 //往数组中放入数字 while (i <= mid && j <= R) { if (vec[i] > vec[j]) { tmp[index++] = vec[j++]; } else { tmp[index++] = vec[i++]; } } while (i <= mid) { tmp[index++] = vec[i++]; } while (j <= R) { tmp[index++] = vec[j++]; } //将临时数组中数字存入原数组 index = L; for (int i = 0; i < (R - L + 1); ++i) { vec[index++] = tmp[i]; }}
void Merge_sort(vector<int> &vec, int L, int R) { //分解到每个数组只有一个元素的时候停止分解 if (L >= R) return; //0 //分解，递归前进进行分解 int mid = (L + R) / 2; //1
Merge_sort(vec, L, mid); //2 Merge_sort(vec, mid + 1, R);//3 //合并，递归回退的过程 Merge(vec, L, mid, R); //4}
int main() { vector<int> vec = {1, 5, 4, 2, 3}; int n = vec.size(); Merge_sort(vec, 0, vec.size() - 1); for (int i = 0; i < n; ++i) { cout << vec[i] << " "; } return 0;}