/* MERGESORT Recursiv = Iterativ*/

#include <stdio.h>
#include <stdlib.h>
int v[500000],w[500000],n;


int MergeSort(int s,int d,int adancime)
{  int m,i,j,ii,jj,c;
   int *vp,*wp;
   if (d-s+1>2) { m=(d+s)/2;
                  MergeSort(s,m,-adancime);
                  MergeSort(m+1,d,-adancime); 
                  ii=m+1,jj=d-m;
                  i=s; j=m+1; c=s;
                  if (adancime>0) {vp=v; wp=w;}
                  else {wp=v; vp=w;}
                  while(i<ii && j<=d)
                                        {  if (wp[i]<wp[j]) { vp[c]=wp[i]; c++; i++;}
                                           else { vp[c]=wp[j]; c++;j++;}
                                              
                                              
                                              
                                        }                
                  if (i==ii)                      
                  for(;j<=d; j++) {vp[c]=wp[j]; c++;}
                  if (j>d)                      
                  for(;i<ii;i++) {vp[c]=wp[i]; c++;}
                  
                }  
   else if(d-s+1==2) { if (adancime>0) {vp=v; wp=w;}
                       else {wp=v; vp=w;}
                       
                       if (wp[s]>wp[d])
                       {vp[s]=wp[d];
                       vp[d]=wp[s];
                       }
        
                     }  
      
     
 return 0;    
     
}

int main()
{ int i; 

  FILE* f=fopen("algsort.in","rt"),*g=fopen("algsort.out","wt");
  //fprintf(g,"kkk");
  fscanf(f,"%i",&n);
  for (i=0;i<n;i++) { fscanf(f,"%i",v+i);
                      w[i]=v[i];
      
                    }
 // fprintf(g,"kkk");                  
  MergeSort(0,n-1,1);
 //fprintf(g,"kkk");
  for(i=0;i<n;i++)
  fprintf(g,"%i ",v[i]);  
    
   fclose(f);
   fclose(g);
   return 0; 
    
    
    
}