本蒟蒻初学归并，所以用的归并来做这题

#include<bits/stdc++.h>
using namespace std;
int n,a[100010],tmp[100010];
void merge(int l,int mid,int r)
{
	//a[l,mid]和a[mid+1,r] 归并，然后放到a[l,r]
	int i=l,j=mid+1,p=l;
	while(i<=mid && j<=r)
	{
		if(a[i]<=a[j])
		{
			tmp[p]=a[i];
			p++;
			i++;
		}
		else
		{
			tmp[p]=a[j];
			p++;
			j++;
		}
	}
	while(i<=mid)
	{
		tmp[p]=a[i];
		p++;
		i++;
	}
	while(j<=r)
	{
		tmp[p]=a[j];
		p++;
		j++;
	}
	for(int i=1;i<=r;i++)
		a[i]=tmp[i];
}
void merge_sort(int l,int r)
{
	//要对a数组的[l,r]区间进行排序
	if(l==r)
		return;
	int mid=(l+r)/2;
	//对[l,mid]排序
	merge_sort(l,mid);
	//对[mid,r]排序
	merge_sort(mid+1,r);
	merge(l,mid,r);
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	merge_sort(1,n);
	for(int i=1;i<=n;i++)
		cout<<a[i]<<" ";
	return 0;
}