详细的注释都写在代码中了
#include<bits/stdc++.h>
using namespace std;
int n;
const int N=1e5;
int q[N],tmp[N];
void merge_sort(int q[],int l,int r)
{
if(l>=r)return;
int mid=(l+r)/2;
merge_sort(q,l,mid);//先进行递归处理
merge_sort(q,mid+1,r);
int k=0;//对于我们递归的每一层,我们进行局部的归并排序,其实递归到最底部 的时候,就是两个数进行比较,然后不断向上进行更新
int i=l;//合并区间的左端点
int j=mid+1;//合并区间的右端点,其实就是双指针算法
while(i<=mid&&j<=r)//只要我们有一个指针不在我们的这个区间里,我们就直接没退出
{
if(q[i]<=q[j])tmp[k++]=q[i++];//tmp保存的是我们当前区间排序后的答案
else tmp[k++]=q[j++];
}
while(i<=mid)tmp[k++]=q[i++];//这种情况就是我们的右指针移到右端点的情况
while(j<=r)tmp[k++]=q[j++];//这种情况就是我们的左端点移动到左端点的情况
for(int i=l,j=0;i<=r;i++,j++)
q[i]=tmp[j];//把我们的答案进行更新
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)//我们的下标是从0开始的,其实从1开始也是可以的,只要改成merge_sort(q,1,n)就行
scanf("%d",&q[i]);
merge_sort(q,0,n-1);
for(int i=0;i<n;i++)
cout<<q[i]<<' ';
return 0;
}