#include <fstream>

void osszeFesul(int * tomb, int bal, int kozep, int jobb){
    int * temp = new int[jobb - bal + 1];
    int indexBal = bal, indexJobb = kozep + 1, indexTemp = 0;
    while(indexBal <= kozep && indexJobb <= jobb)
        if(tomb[indexBal] <= tomb[indexJobb])
            temp[indexTemp++] = tomb[indexBal++];
        else
            temp[indexTemp++] = tomb[indexJobb++];
    while(indexBal <= kozep)
        temp[indexTemp++] = tomb[indexBal++];
    while(indexJobb <= jobb)
        temp[indexTemp++] = tomb[indexJobb++];
    for(int i = 0; i < indexTemp; i++) tomb[bal + i] = temp[i];

    delete [] temp;
}

void mergeSort(int * tomb, int bal, int jobb){
    if(bal >= jobb)
        return;
    int kozep = (bal + jobb) / 2;
    mergeSort(tomb, bal, kozep);
    mergeSort(tomb, kozep + 1, jobb);
    osszeFesul(tomb, bal, kozep, jobb);
}

int main(){
    std::ifstream bem("algsort.in");
    std::ofstream kim("algsort.out");
    int n;
    bem >> n;
    int * tomb = new int[n];
    for(int i = 0; i < n; i++)  bem >> tomb[i];
    mergeSort(tomb, 0, n - 1);

    for(int i = 0; i < n; i++)  kim << tomb[i] << ' ';

    bem.close();
    kim.close();
    delete [] tomb;
}