#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[l] < arr[(l + r) / 2]) {
        if (arr[(l + r) / 2] < arr[r]) {
            val = arr[(l + r) / 2];
            std::swap(arr[(l + r) / 2], arr[l]);
        } else {
            if (arr[r] < arr[l]) {
                val = arr[l];
            } else {
                val = arr[r];
                std::swap(arr[r], arr[l]);
            }
        }
    } else {
        if (arr[l] < arr[r]) {
            val = arr[l];
        } else {
            if (arr[r] < arr[(l + r) / 2]) {
                val = arr[(l + r) / 2];
                std::swap(arr[(l + r) / 2], arr[l]);
            } else {
                val = arr[r];
                std::swap(arr[r], 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 (r - l < 4) {
        for (int i = r; i > l; i--) {
            for (int j = l; j < i; j++) {
                if (arr[j] > arr[j + 1]) std::swap(arr[j], arr[j + 1]);
            }
        }

        return;
    }

    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] << ' ';
}