#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

void merge(vector<int> &d, int stanga, int mij, int dreapta)
{
    int i, j, k;
    int n1 = mij - stanga + 1;
    int n2 = dreapta - mij;

    vector<int> L(n1), R(n2); //vectori temporari L si R

    for (i = 0; i < n1; i++)
        L[i] = d[stanga + i]; //copiaza elem in vectorul temporar
    for (j = 0; j < n2; j++)
        R[j] = d[mij + 1 + j]; // copiaza elem in vectorul temporar

    i = 0;
    j = 0;
    k = stanga;

    while (i < n1 && j < n2) // pana cand avem elemente in R si L
    {
        if (L[i] <= R[j]) 
        {
            d[k] = L[i];
            i++;
        }
        else
        {
            d[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) // elementele ramase
    {
        d[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) // elementele ramase
    {
        d[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(vector<int> &d, int stanga, int dreapta)
{
    if (stanga < dreapta)
    {
        int mij = (dreapta - stanga) / 2 +1;

        mergeSort(d, stanga, mij);
        mergeSort(d, mij + 1, dreapta);
        merge(d, stanga, mij, dreapta);
    }
}

int main()
{
    int n;
    vector<int> d;

    ifstream fin("mergesort.in");
    fin >> n;
    d.resize(n);

    for (int i = 0; i < n; i++)
    {
        fin >> d[i];
    }

    mergeSort(d, 0, n - 1);

    ofstream fout("mergesort.out");

    for (int i = 0; i < n; i++)
    {
        fout << d[i] << " ";
    }

    return 0;
}