//
// main.cpp
// acwing归并排序
//
// Created by 战泰霖 on 2021/1/23.
//分治
//1.先从中间分,递归排序左边和右边
//2.归并合二为一
//双指针算法
//归并排序是稳定的
include [HTML_REMOVED]
using namespace std;
const int N = 1000010;
int n;
int q[N],tmp[N];
void merge_sort(int q[],int l,int r)
{
if(l>=r)return;
int mid = (l+r)>>1;
merge_sort(q,l,mid),merge_sort(q,mid+1,r);
int k = 0,i = l , j = mid+1;
while(i<=mid && j<=r)
{
if(q[i]>=q[j])tmp[k++]=q[j++];
else tmp[k++]=q[i++];
}
while(i <= mid)tmp[k++]=q[i++];
while(j <= r)tmp[k++] = q[j++];
for(i=l,j=0;i<=r;i++,j++)q[i]=tmp[j];
}
int main()
{
scanf(“%d”,&n);
for(int i=0;i<n;i++)scanf("%d",&q[i]);
merge_sort(q,0,n-1);
for(int i=0;i<n;i++)printf("%d ",q[i]);
return 0;
}