void merge(int A[],int p,int q,int r){
  int n1=q-p+1;
  int n2=r-q;
  int i,j,k;
  int* L;
  int* R;
  L=(int*)malloc(sizeof(int)*(n1+1));
  R=(int*)malloc(sizeof(int)*(n2+1));

/*  int *L=new int[n1+1];
  int *R=new int[n2+1];
*/                     /*此为C++语言，等价于上面的malloc*/
  for(i=0;i<n1;i++)
    L[i]=A[p+i];       /*数组A[p...q]对应于数组L[0...n1-1]*/
  for(j=0;j<n2;j++)
    R[j]=A[q+j+1];     /*数组A[q+1...r]对应于数组R[0...n2-1]*/
  L[n1]=N;
  R[n2]=N;         /*设置两个大数，称为哨兵牌，用于简化代码，一旦发生两张哨兵牌
                   同时出现的情况是，说明两堆牌中的所有非哨兵牌都放到了堆中去了
                   */
  i=0;
  j=0;
  for(k=p;k<=r;k++)
    {
    if(L[i]<=R[j])
      {
      A[k]=L[i];
      i++;
      }
    else{
      A[k]=R[j];
      j++;
      }
    }
}

void merge_sort(int A[],int p,int r)
{
  int q;
  if(p<r)
  {
  /*q=(int)((p+r)/2);   下取整可用floor()，上取整可用ceil()，包含在math.h中*/
  q=floor((float)(p+r)/2.0);
  merge_sort(A,p,q);
  merge_sort(A,q+1,r);
  merge(A,p,q,r);
  }
}

/*
void main()
{
   int a[10]={12,78,20,24,158,50,58,621,1475,2};
   int i;
   printf("排序前数组序列：\n");
   for(i=0;i<10;i++)
   {
      printf("%5d",a[i]);
   } 
   printf("\n排序前数组序列：\n");
   merge_sort(a,0,9);
   for(i=0;i<10;i++)
   {
      printf("%5d",a[i]);
   }
  
   getchar();
  
}
*/
  void main(){
  int* B;
  int a;
  int n;
  scanf("%d",&n);
  if(NULL==(B=(int*)malloc(sizeof(int)*n)))
    {
    printf("memory error!\n");
    exit(1);
    }
  for(a=0;a<n;a++)
    scanf("%d",&B[a]);
  merge_sort(B,0,n-1);
  for(a=0;a<n;a++)
    printf("%6d",B[a]);
  getchar();
  getchar();       /*用于完成计算后等待查看结果，输入一个数结束程序，退出显示页面*/
}