#include <fstream>

std::ifstream in("algsort.in");
std::ofstream out("algsort.out");

int n, arr[500000];

int partition(int* arr, int l, int r) {
    int val;
    if (arr[r] > arr[l] && arr[r] > arr[(l + r) / 2]) {
        val = arr[r];
        std::swap(arr[r], arr[l]);
    } else if (arr[(l + r) / 2] > arr[l]) {
        val = arr[(l + r) / 2];
        std::swap(arr[(l + r) / 2], arr[l]);
    } else {
        val = arr[l];
    }
    int dr = r;
    int i = l + 1;
    while (i <= dr) {
        if (arr[i] < val)
            std::swap(arr[i], arr[i - 1]), i++;
        else
            std::swap(arr[i], arr[dr--]);
    }

    return dr;
}

void quicksort(int* arr, int l, int r) {
    if (l >= r) return;

    if (r - l < 5) {
        for (int i = r; i > l; i--) {
            for (int j = l; j < i; j++) {
                if (arr[i] > arr[i + 1]) std::swap(arr[i], arr[i + 1]);
            }
        }
    }

    int mid = partition(arr, l, r);
    quicksort(arr, l, mid - 1);
    quicksort(arr, mid + 1, r);
}

int main() {
    in >> n;
    for (int i = 0; i < n; i++) in >> arr[i];

    quicksort(arr, 0, n - 1);

    for (int i = 0; i < n; i++) out << arr[i] << ' ';
}