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

void insertion_sort (signed int *begin, signed int *end)
{
    const unsigned char SIZE(end - begin);
    signed int *array(new signed int [SIZE]), *it(array), *position, *start(begin), value;
    do
    {
        value = *begin;
        for (position = it - 1 ; position >= array && *position > value ; --position)
            position[1] = *position;
        position[1] = value;
        ++begin;
        ++it;
    }
    while (begin < end);
    it = array;
    do
    {
        *start = *it;
        ++start;
        ++it;
    }
    while (start < end);
    delete [ ] array;
}

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

void quicksort (signed int *begin, signed int *end)
{
    static const unsigned char GROUP(5);
    signed int *pivot(partition(begin,end));
    if (pivot - begin <= GROUP)
        insertion_sort(begin,pivot);
    else
        quicksort(begin,pivot);
    if (end - pivot <= GROUP)
        insertion_sort(pivot,end);
    else
        quicksort(pivot,end);
}

int main (void)
{
    unsigned int 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();
    quicksort(v,end);
    --end;
    it = v;
    std::ofstream output("algsort.out");
    while (true)
    {
        output << *it;
        if (it == end)
            break;
        output.put(' ');
        ++it;
    }
    delete [ ] v;
    output.put('\n');
    output.close();
    return 0;
}