#include <iostream>
#include <fstream>
#include <random>
#include <bits/stdc++.h>


using namespace std;

ifstream f("algsort.in");
ofstream g("algsort.out");

const int MAX_N = 500003;
int v[MAX_N] = {0};
int n;

void insertionSort(int left, int right) {
    for(int i = left + 1; i <= right; i++) {
        int key = v[i];
        int j = i - 1;
        while(j >= left && v[j] > key) {
            v[j+1] = v[j];
            j--;
        }
        v[j+1] = key;
    }
}

void quicksort(int left, int right) {
    if(left >= right) return;
    if(right - left + 1 < 10) {
        insertionSort(left, right);
        return;
    }
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    int pivot = left + rng() % (right - left + 1);
    int i = left - 1, j = right + 1;
    while(true) {
        do {
            i++;
        } while(v[i] < v[pivot]);
        do {
            j--;
        } while(v[j] > v[pivot]);
        if(i >= j) break;
        swap(v[i], v[j]);
    }
    quicksort(left, j);
    quicksort(j+1, right);
}

int main() {
    f >> n;
    for(int i = 0; i < n; i++) {
        f >> v[i];
    }
    quicksort(0, n-1);
    for(int i = 0; i < n; i++) {
        g << v[i] << " ";
    }
    return 0;
}