#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("algsort.in");
ofstream fout("algsort.out");

inline int getRandomNumber(int lowerBound, int upperBound) {
    return lowerBound + rand() % (upperBound - lowerBound + 1);
}

class Sorter {
public:
    virtual vector<int> sort(const vector<int>& numbers) const = 0;

    virtual ~Sorter() = default;
};

class MergeSorter : public Sorter {
public:
    vector<int> sort(const vector<int>& numbers) const override {
        vector<int> sortedNumbers(numbers);
        sort(sortedNumbers, 0, (int)numbers.size() - 1);
        return sortedNumbers;
    }

private:
    void sort(vector<int>& numbers, int leftIndex, int rightIndex) const {
        // cout << leftIndex << " " << rightIndex << "\n";
        if (leftIndex >= rightIndex) {
            return;
        }

        int middleIndex = (leftIndex + rightIndex) / 2;
        sort(numbers, leftIndex, middleIndex);
        sort(numbers, middleIndex + 1, rightIndex);
        merge(numbers, leftIndex, rightIndex);
    }

    void merge(vector<int>& numbers, int leftIndex, int rightIndex) const {
        if (leftIndex >= rightIndex) {
            return;
        }

        int middleIndex = (leftIndex + rightIndex) / 2;

        vector<int> mergedValues(rightIndex - leftIndex + 1);
        int mergedValuesIndex = 0;

        int currentLeftHalfIndex = leftIndex;
        int currentRightHalfIndex = middleIndex + 1;
        while (currentLeftHalfIndex <= middleIndex && currentRightHalfIndex <= rightIndex) {
            if (numbers[currentLeftHalfIndex] <= numbers[currentRightHalfIndex]) {
                mergedValues[mergedValuesIndex++] = numbers[currentLeftHalfIndex++];
            } else {
                mergedValues[mergedValuesIndex++] = numbers[currentRightHalfIndex++];
            }
        }
        while (currentLeftHalfIndex <= middleIndex) {
            mergedValues[mergedValuesIndex++] = numbers[currentLeftHalfIndex++];
        }
        while (currentRightHalfIndex <= rightIndex) {
            mergedValues[mergedValuesIndex++] = numbers[currentRightHalfIndex++];
        }

        for (int i = leftIndex; i <= rightIndex; i++) {
            numbers[i] = mergedValues[i - leftIndex];
        }
    }
};

class QuickSorter : public Sorter {
public:
    QuickSorter() {
        srand(time(NULL));
    }

    vector<int> sort(const vector<int>& numbers) const override {
        vector<int> sortedNumbers(numbers);
        sort(sortedNumbers, 0, numbers.size() - 1);
        return sortedNumbers;
    }

private:
    void sort(vector<int>& numbers, int leftIndex, int rightIndex) const {
        if (leftIndex >= rightIndex) {
            return;
        }
        int pivotIndex = getRandomNumber(leftIndex, rightIndex);

        // put the pivot on its correct index
        int countLowerThanPivot = countLowerThan(numbers, leftIndex, rightIndex, numbers[pivotIndex]);
        int correctPivotIndex = leftIndex + countLowerThanPivot;
        swap(numbers[pivotIndex], numbers[correctPivotIndex]);
        pivotIndex = correctPivotIndex;

        arrangeNumbersAroundCorrectlyPlacedPivot(numbers, leftIndex, rightIndex, pivotIndex);

        sort(numbers, leftIndex, pivotIndex - 1);
        sort(numbers, pivotIndex + 1, rightIndex);
    }

    // Ensures all numbers smaller than the pivot are before the correctly placed pivot (which implies that all larger or equal numbers are afterwards)
    void arrangeNumbersAroundCorrectlyPlacedPivot(vector<int>& numbers, int leftIndex, int rightIndex, int pivotIndex) const {
        int currentLeftHalfIndex = leftIndex;
        int currentRightHalfIndex = pivotIndex + 1;
        while (currentLeftHalfIndex < pivotIndex) {
            if (numbers[currentLeftHalfIndex] >= numbers[pivotIndex]) {
                swap(numbers[currentLeftHalfIndex], numbers[currentRightHalfIndex]);
                currentRightHalfIndex++;
            } else {
                currentLeftHalfIndex++;
            }
        }
    }

    static int countLowerThan(const vector<int>& numbers, int leftIndex, int rightIndex, int threshold) {
        int count = 0;
        for (int i = leftIndex; i <= rightIndex; i++) {
            if (numbers[i] < threshold) {
                count++;
            }
        }
        return count;
    }
};

void sortAndPrint(const vector<int>& numbers, const Sorter& sorter) {
    vector<int> sortedNumbers = sorter.sort(numbers);
    // cout << "printing with size " << sortedNumbers.size() << "\n";
    for (int number : sortedNumbers) {
        fout << number << " ";
    }
}

int main() {
    int n;
    fin >> n;
    vector<int> numbers(n);
    for (int i = 0; i < n; i++) {
        fin >> numbers[i];
    }

    sortAndPrint(numbers, QuickSorter());

    return 0;
}