#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

vector <vector <int> > a;
int s;

void read()
{
    int n;
    ifstream cin("algsort.in");
    cin >> n;
    s = sqrt(n);
    a.resize(s + 5);

    for (size_t i = 0; i < a.size(); i++)
    {
        int x;
        cin >> x;
        a[i / s].push_back(x);
    }

    cin.close();
}

void qs(vector <int> &a)
{
    if (a.size() < 100)
    {
        for (size_t i = 0; i < a.size(); i++)
            for (size_t j = i + 1; j < a.size(); j++)
                if (a[j] < a[i]) swap(a[j], a[i]);

        return;
    }

    vector <int> x, z;
    int y = 0, q = a[a.size() / 2];

    for (; !a.empty(); )
    {
        int last = a[a.size() - 1];
        if (last == q) y++;
        if (last > q) z.push_back(last);
        if (last < q) x.push_back(last);
        a.pop_back();
    }

    qs(x);
    qs(z);

    for (size_t i = 0; i < x.size() / 2; i++)
        swap(x[i], x[x.size() - 1 - i]);
    for (size_t i = 0; i < z.size() / 2; i++)
        swap(z[i], z[z.size() - 1 - i]);

    for (; !x.empty(); )
    {
        int q = x[x.size() - 1];
        a.push_back(q);
        x.pop_back();
    }
    for (; y; y--)
        a.push_back(q);
    for (; !z.empty(); )
    {
        int q = z[z.size() - 1];
        a.push_back(q);
        z.pop_back();
    }
}

void srt()
{
    for (int i = 0; i < a.size(); i++)
        qs(a[i]);

    vector <int> q = a[0];
    for (size_t i = 1; i < a.size(); i++)
    {
        q.resize(q.size() + a[i].size());
        merge(q.begin(), q.end(), a[i].begin(), a[i].end(), q.begin());
    }

    ofstream cout("algsort.out");

    for (size_t i = 0; i < q.size(); i++)
        cout << q[i] << ' ';

    cout.close();
}

int main()
{
    read();

    srt();

    return 0;
}