#include <iostream>
#include <fstream>

using namespace std;
int mij, v1[10000], cnt=0, v[10000];
void merge(int v[], int left, int mij, int right){
int i=left, j=mij+1, cnt=0;
while(i<=mij && j<=right){
while(v[i]<=v[j] && i<=mij){
    cnt++;
    v1[cnt]=v[i];
    i++;
}
while(v[j]<=v[i] && j<=right){
    cnt++;
    v1[cnt]=v[j];
    j++;
}
}
while(i<=mij){
    cnt++;
    v1[cnt]=v[i];
    i++;
}
while(j<=right){
     cnt++;
    v1[cnt]=v[j];
    j++;
}
for(int i=1; i<=cnt; i++){
    v[left+i-1]=v1[i];
} //cout<<cnt<<" ";
}
void mergesort(int v[], int left, int right){
    if(left>=right)
        return ;
    mij=(left+right-1)/2;
    mergesort(v, left, mij);
    mergesort(v, mij+1, right);
    merge(v, left, mij+1, right);

}
int main()
{
    ifstream in("algsort.in");
    ofstream out("mergesort.out");
     int n, a, i;
     in>>n;
     for(i=1; i<=n; i++){
        in>>v[i];
     }
     mergesort(v, 1, n);
     merge(v, 1, n/2, n);
     for(i=1; i<=n; i++)
        out<<v[i]<<" ";
    return 0;
}