#include<fstream.h>
#include<stdlib.h>

void msort(int *v,int nv)
{
  int *aux, i, is, j, js, k, size, *s, *d, *paux, x;
  aux=(int*)malloc(sizeof(int)*nv);
  for(i=0;i+1<nv;i+=2)if(v[i]>v[i+1]){
                                     j=v[i];
                                     v[i]=v[i+1];
                                     v[i+1]=j;
                                     }
  s=v;
  d=aux;
  size=2;
  while(size<nv)
       {
       i=k=0;
       j=size;
       do{
         is=i+size;
         js=j+size; 
         while(i<is && j<js)if(s[i]<=s[j])d[k++]=s[i++];
                            else d[k++]=s[j++];
         if(i<is)do d[k++]=s[i++];while(i<is);
         else while(j<js)d[k++]=s[j++];
         i=k=j;
         j+=size;
         } while(j<nv);
       size*=2;
       paux=s;
       s=d;
       d=paux;
       }
  if(s==aux)for(i=0;i<nv;i++)v[i]=aux[i];
}

int main()
{
  int i, nv, *v;
  ifstream f("algsort.in");
  ofstream g("algsort.out");
  f>>nv;
  v=(int*)malloc(sizeof(int)*nv);
  for(i=0;i<nv;i++)f>>v[i];
  msort(v,nv);
  for(i=0;i<nv;i++)g<<v[i]<<' ';
}