#include<stdio.h>
#include<stdlib.h>

typedef int(*TFComp)(const void *, const void *);

int cmp(const void *a, const void *b)
{ 
  if((*(int*)a)> (*(int*)b)) return 1;
  if((*(int*)a)< (*(int*)b)) return -1;
  return 0;
}

void msort(int *v,int nv)
{
  int *aux, *p, *pfin, *q, *qfin, *r, *fin, *s, *d, *paux, vaux, size;
  aux=(int*)malloc(sizeof(int)*nv);
  for(p=v,pfin=v+nv-1; p<pfin; p+=2)if(*p>*(p+1)){
                                                 vaux=*p;
                                                 *p=*(p+1);
                                                 *(p+1)=vaux;
                                                 }
  s=v;
  d=aux;
  size=2;
  while(size<nv)
       {
       p=s;
       q=s+size;
       r=d;
       fin=s+nv;
       do{
	     pfin=p+size;
         if(q+size<=fin)qfin=q+size;
	     else qfin=fin; 
         while(p<pfin && q<qfin)if(*p<=*q){*r=*p;r++;p++;}
                                else {*r=*q;r++;q++;}
         if(p<pfin)do {*r=*p;r++;p++;} while(p<pfin);
         else while(q<qfin){*r=*q;r++;q++;}
         p=q;
         q+=size;
	     } while(q<fin);
       while(p<fin){*r=*p;r++;p++;}
       size=size*2;
       paux=s;
       s=d;
       d=paux;
       }
  if(s==aux)for(p=v,q=aux,fin=v+nv;p<fin;p++,q++)*p=*q;
  free(aux);
}

int main()
{
  FILE *f,*g;
  int i,nv,*v;
  f=fopen("algsort.in","rt");
  g=fopen("algsort.out","wt");
  fscanf(f,"%i",&nv);
  v=(int*)malloc(sizeof(int)*nv);
  for(i=0;i<nv;i++)fscanf(f,"%i",v+i);
  msort(v,nv);
  for(i=0;i<nv;i++)fprintf(g,"%i ",v[i]);
  return 0;
}