今天下午学习了一下归并排序算法，感觉思想很简单就是采用分治法，先将所有数据拆分开，然后二路合并。但是当我看到实现代码的时候，在递归那有点不理解 ，晚上又看了看终于清楚知道了递归的代码实现原理。
所以下面就讲一讲自己理解的归并排序算法中的递归（如有错误，欢迎批评指正）
//这里代码参考大佬的博客写了写：
#include <iostream>
using namespace std;
int n;
void mergeSort(int arr[],int l,int mid,int r){
//建立一个临时存储数组
int *temp=new int[n];
int p1=l;
int p2=mid+1;
int p=0;
while(p1<=mid&&p2<=r){
if(arr[p1]<=arr[p2]){
temp[p++]=arr[p1++];
}else{
temp[p++]=arr[p2++];
}
}
while(p1<=mid){
temp[p++]=arr[p1++];
}
while(p2<=r){
temp[p++]=arr[p2++];
}
for(int i=0;i<p;i++){
//存入数组
arr[i+l]=temp[i];
}
}
void merge(int arr[],int l,int r){
if(l>=r){
return;
}
int mid=(l+r)/2;
//左边拆分
merge(arr,l,mid);
//右边拆分
merge(arr,mid+1,r);
//合并并排序
mergeSort(arr,l,mid,r);
}
int main()
{
cin>>n;
int *arr=new int[n];
for(int i=0;i<n;i++){
cin>>arr[i];
}
merge(arr,0,n-1);
for(int i=0;i<n;i++){
cout<<arr[i]<<" ";
}
return 0;
}
3，5，7，2，8，1，4，6
八个数从小到大排序
一、
1、首先主函数中调用函数 merge(arr,0,7)
2、mid=3，调用函数merge(arr,0,3)
3、mid=1，调用函数merge(arr,0,1)
4、mid=0，调用函数merge(arr,0,0)， 符合if条件 return 跳出
5、进入下一个函数merge(arr,1,1)，符合if条件 return跳出
6、进入合并排序函数 mergeSort(arr,0,1,1),排序——3，5
7、返回上一步 merge(arr,2,3)
8、mid=2，调用函数merge(arr,2,2),符合if条件 return跳出
9、进入下一个函数merge(arr,3,3) 符合if条件 return跳出
10、进入合并排序函数 mergeSort(arr,2,2,3), 排序——2,7
11、返回上一步 mergeSort(arr,0,1,3)，排序(3,5|2,7)——2,3,5,7
二、
1、返回上一步，调用函数merge(arr,4,7)
2、mid=5，调用函数merge(arr,4,5)
3、mid=4，调用函数merge(arr,4,4)，符合if条件 return跳出
4、进入下一个函数merge(arr,5,5),符合if条件 return跳出
5、进入合并排序函数mergeSort(arr,4,4,5),排序——1，8
6、返回上一步merge(arr,6,7)
7、mid=6，调用函数merge(arr,6,6),符合if条件return跳出
8、进入下一个函数merge(arr,7,7),符合if条件return跳出
9、进入合并排序函数mergeSort(arr,6,6,7),排序——4,6
10、返回上一步mergeSort(arr,4,5,7),排序(1,8|4,6)——1，4，6，8
1、返回上一步mergeSort(0,7),排序(2，3，5，7|1，4，6，8)——1，2，3，4，5，6，7，8
注:
p1指针指向第一个序列开头，l=0；
p2指针指向mid+1=4；
p指针指向临时数组的开头；
2先和1比，1小 存入临时数组 p++,p2++,
2再和4比，2小 存入临时数组 p++,p1++,
4和3比，3小 存入临时数组 p++,p1++,
5和4比，4小 存入临时数组 p++,p2++,
5和6比，5小 存入临时数组 p++,p1++,
7和6比，6小 存入临时数组 p++,p2++,
7和8比，7小 存入临时数组 p++,p1++,
p==7；
p1=4>mid=3，跳出while循环
将第二个序列中剩下的数据(8)按顺序存入临时数组
再将临时数组中的数据依次存入数组中
{数组下标从i+l开始，l=0}——1，2，3，4，5，6，7，8
2、排序完成输出打印