//Sortarea prin interclasare
#include<fstream>
#define nmax 500001

using namespace std;

ifstream fin("algsort.in");
ofstream fout("algsort.out");

int a[nmax],n;

void citire()
{fin>>n;
for(int i=1;i<=n;i++)
  fin>>a[i];
}

void afisare()
{for(int i=1;i<=n;i++)
   fout<<a[i]<<" ";
}

void interclasare(int st,int mijl,int dr)
{int b[nmax];
int i,j,k;
for(i=st,j=mijl+1,k=1;i<=mijl && j<=dr;k++)
  if(a[i]<a[j])
     {b[k]=a[i];
      i++;
     }
   else
     {b[k]=a[j];
      j++;
     }
while(i<=mijl)
  {b[k]=a[i];
   i++;k++;
  }
while(j<=dr)
  {b[k]=a[j];
   j++;k++;
  }
for(i=st;i<=dr;i++)
  a[i]=b[i-st+1];
}

void merge_sort(int st,int dr)
{if(st<dr)
   {int mijl=(st+dr)/2;
    merge_sort(st,mijl);
    merge_sort(mijl+1,dr);
    interclasare(st,mijl,dr);
   }
}

int main()
{citire();
merge_sort(1,n);
afisare();
fin.close();
fout.close();
return 0;
}