#include <iostream>
#include <fstream>
using namespace std;
const int maxhossz=500000;
void fesules(int eredmeny[], int elso[], int masodik[], int nelso, int nmasodik);
void mergesort(int tomb[], int n)
{
    if (n == 1)
        return;

    int *elsoresz = new int[n/2];
    int *masodikresz = new int[n - n/2];

    for (int i = 0; i < n/2; i++)
    {
        elsoresz[i] = tomb[i];
    }
    for (int i = n/2; i < n; i++)
    {
        masodikresz[i-n/2] = tomb[i];
    }
    mergesort(elsoresz, n/2);
    mergesort(masodikresz, n-n/2);
    fesules(tomb, elsoresz, masodikresz, n/2, n-n/2);

    delete[] elsoresz;
    delete[] masodikresz;
}
void fesules(int eredmeny[], int elso[], int masodik[], int nelso, int nmasodik)
{
    int indexelso = 0 , indexmasodik = 0;
    for (int i = 0; i < nelso + nmasodik; i++)
    {
        if (indexelso >= nelso)
        {
            eredmeny[i] = masodik[indexmasodik];
            indexmasodik++;
        }
        else if (indexmasodik >= nmasodik)
        {
            eredmeny[i] = elso[indexelso];
            indexelso++;
        }
        else if (elso[indexelso] < masodik[indexmasodik])
        {
            eredmeny[i] = elso[indexelso];
            indexelso++;
        }
        else
        {
            eredmeny[i] = masodik[indexmasodik];
            indexmasodik++;
        }
    }
}

int main()
{
    ifstream be ("algsort.in");
    ofstream ki ("algsort.out");
    int n, tomb[maxhossz];
    be >> n;
    for (int i = 0; i < n; i++)
        be >> tomb[i];
    mergesort(tomb, n);
    for (int i = 0; i < n; i++)
        ki << tomb[i] << " ";
    return 0;
}