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

using namespace std;

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



void readData(vector <int> &array) {
    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(vector <int> &array, 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(vector <int> &array, int beginIndex, int endIndex) {
    if(beginIndex < endIndex) {
        int pivot = partition(array, beginIndex, endIndex);
        quickSort(array, beginIndex, pivot);
        quickSort(array, pivot + 1, endIndex);
    }

}

void mergeSort(vector <int> &array, int beginIndex, int endIndex) {
    if(endIndex == beginIndex)
        return;

    int pivot = beginIndex + (endIndex - beginIndex) / 2;
    mergeSort(array, beginIndex, pivot);
    mergeSort(array, pivot + 1, endIndex);

    vector <int> aux;
    for(int left1 = beginIndex, left2 = pivot + 1; left1 <= pivot || left2 <= endIndex; ) {
        if(left2 > endIndex || (left1 <= pivot && array[left1] < array[left2]))
            aux.push_back(array[left1++]);
        else
            aux.push_back(array[left2++]);
    }

    for(int i = beginIndex, j = 0; i <= endIndex; ++i, ++j)
        array[i] = aux[j];
}

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

int main() {
    vector <int> array;
    readData(array);
    //quickSort(array, 0, array.size() - 1);
    mergeSort(array, 0, array.size() - 1);
    writeData(array);
    return 0;
}