#include <fstream>
#include <cstdlib>
#include <ctime>

signed int *partition (signed int *begin, signed int *end)
{
    --end;
    if (end == begin)
        return begin;
    std::srand(std::time(0));
    signed int *pivot(begin + std::rand() % (end - begin));
    if (*pivot != *end)
    {
        *pivot ^= *end;
        *end ^= *pivot;
        *pivot ^= *end;
    }
    signed int *left_side(begin), *it(begin);
    signed int pivot_value(*end);
    do
    {
        if (*it <= pivot_value)
        {
            if (*it != *left_side)
            {
                *it ^= *left_side;
                *left_side ^= *it;
                *it ^= *left_side;
            }
            ++left_side;
        }
        ++it;
    }
    while (it < end);
    if (*end != *left_side)
    {
        *end ^= *left_side;
        *left_side ^= *end;
        *end ^= *left_side;
    }
    return left_side;
}

signed int *get_median (signed int *begin, signed int *end)
{
    signed int *median(begin + ((end - begin) >> 1)), *pivot(partition(begin,end));
    while (true)
    {
        if (pivot > median)
            end = pivot;
        else if (pivot < median)
             begin = pivot + 1;
        else
            break;
        pivot = partition(begin,end);
    }
    return median;
}

void median_sort (signed int *begin, signed int *end)
{
    if (begin == end - 1)
        return;
    signed int *median(get_median(begin,end));
    median_sort(begin,median);
    median_sort(median,end);
}

int main (void)
{
    unsigned short n;
    std::ifstream input("algsort.in");
    input >> n;
    signed int *v(new signed int [n]), *it(v), *end(v + n);
    do
    {
        input >> *it;
        ++it;
    }
    while (it < end);
    input.close();
    median_sort(v,end);
    std::ofstream output("algsort.out");
    it = v;
    --end;
    while (true)
    {
        output << *it;
        if (it == end)
            break;
        output.put(' ');
        ++it;
    }
    delete [ ] v;
    output.put('\n');
    output.close();
    return 0;
}