//Sa se sorteze crescator un sir de n nr intregi
//folosind sortarea prin interclasare . O(nlogn)
#include<fstream>
#define nmax 500001

using namespace std;

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

unsigned int a[nmax],n;

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

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

void interclasare(unsigned int st,unsigned int mijl,unsigned int dr)
{unsigned int b[nmax],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++;
   }
k--;
for(i=st;i<=dr;i++)
  a[i]=b[i-st+1];
}

void sort(unsigned int st,unsigned int dr)
{if(dr-st>1) //daca secventa contine mai mult de un element
   {unsigned int mijl=(st+dr)/2; //calculez mijlocul
    sort(st,mijl);//sortez prima jumatate
    sort(mijl+1,dr);//sortez a doua jumatate
    interclasare(st,mijl,dr); //interclasez cele doua jumatati si obtin
                              //secv st...dr sortata
   }
}

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