#include <stdio.h>
#include <stdlib.h>
#include <vector>

using namespace std;

const char infile[] = "algsort.in";
const char outfile[] = "algsort.out";

vector <int> array;

void readData() {
    FILE *f = fopen(infile, "rt");
    int size, value;
    fscanf(f, "%d", &size);
    for(int i = 0; i < size; ++i) {
        fscanf(f, "%d", &value);
        array.push_back(value);
    }
}

int partition(int beginIndex, int endIndex) {
    int left = beginIndex - 1, right = endIndex + 1;
    int randomValue = array[beginIndex + rand() % (endIndex - beginIndex + 1)];
    while(1) {
        do left++;
        while(array[left] < randomValue);
        do right--;
        while(array[right] > randomValue);
        if(left < right)
            swap(array[left], array[right]);
        else
            return right;
    }
    return left;
}

void quickSort(int beginIndex, int endIndex) {
    if(beginIndex < endIndex) {
        int pivot = partition(beginIndex, endIndex);
        quickSort(beginIndex, pivot);
        quickSort(pivot + 1, endIndex);
    }

}

void writeData() {
    FILE *f = fopen(outfile, "wt");
    for(int i = 0; i < array.size(); ++i)
        fprintf(f, "%d ", array[i]);
}

int main() {
    readData();
    quickSort(0, array.size() - 1);
    writeData();
    return 0;
}