// Merge sort
#include <fstream>

using namespace std;

void mergeSort(int left, int right, int a[]);
void merge(int left, int right, int a[]);

int main()
{
    int N, i;
    ifstream f("algsort.in");
    f >> N;
    int a[N];
    for (i = 0; i < N; i++)
        f >> a[i];
    f.close();
    mergeSort(0, N - 1, a);

    ofstream g("algsort.out");
    for (i = 0; i < N; i++)
        g << a[i] << " ";
    g.close();

    return 0;
}

void mergeSort(int left, int right, int a[])
{
    if (left < right)
    {
        int middle = (left + right) / 2;
        mergeSort(left, middle, a);
        mergeSort(middle + 1, right, a);
        merge(left, right, a);
    }
}

void merge(int left, int right, int a[])
{
    int i, j, k = 0;
    int middle = (left + right) / 2;

    int bLen = middle - left + 1, cLen = right - middle;
    int b[bLen], c[cLen];

    for (i = left; i <= middle; i++)
        b[k++] = a[i];
    k = 0;
    for (j = middle + 1; j <= right; j++)
        c[k++] = a[j];

    i = 0;
    j = 0;
    k = left;
    while (i < bLen && j < cLen)
    {
        if (b[i] < c[j])
            a[k++] = b[i++];
        else
            a[k++] = c[j++];
    }

    while (i < bLen)
        a[k++] = b[i++];
    while (j < cLen)
        a[k++] = c[j++];

}