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

#define MAXN 500001

void imsort (int v[], int l, int r);
void wsort (int v[], int l, int r, int w);
void wmerge (int v[], int i, int m, int j, int n, int w);

void swap (int v[], int i, int j) {
    int aux = v[i];
    v[i] = v[j];
    v[j] = aux;
}

void imsort (int v[], int l, int r) {
    int m, n, w;
    if (r - l > 1) {
        m = l + (r - l) / 2;
        w = l + r - m;
        wsort(v, l, m, w); /* the last half contains sorted elements */
        while (w - l > 2) {
            n = w;
            w = l + (n - l + 1) / 2;
            wsort(v, w, n, l); /* the first half of the previous working area contains sorted elements */
            wmerge(v, l, l + n - w, n, r, w);
        }
        for (n = w; n > l; n--)
            for (m = n; m < r && v[m] < v[m - 1]; m++)
                swap(v, m, m - 1);
    }
}

/* 
 * sort v[l, u), and put result to working area w. 
 * constraint, len(w) == u - l
 */
void wsort (int v[], int l, int r, int w) {
    int m;
    if (r - l > 1) {
        m = l + (r - l) / 2;
        imsort(v, l, m);
        imsort(v, m, r);
        wmerge(v, l, m, m, r, w);
    } else
        while (l < r)
            swap(v, l++, w++);
}

/*
 * merge two sorted subs v[i, m) and v[j...n) to working area v[w...] 
 */
void wmerge (int v[], int i, int m, int j, int n, int w) {
    while (i < m && j < n)
        swap(v, w++, v[i] < v[j] ? i++ : j++);
    while (i < m)
        swap(v, w++, i++);
    while (j < n)
        swap(v, w++, j++);
}

void read_input (int v[], int *n) {
    FILE *fdin = fopen("algsort.in", "r");

    int i;
    fscanf(fdin, "%d", n);
    for (i = 0; i < *n; i++) fscanf(fdin, "%d", &v[i]);
    fclose(fdin);
}

int main () {

    int v[MAXN], n, i;
    read_input(v, &n);
    imsort(v, 0, n);
    
    FILE *fdout = fopen("algsort.out", "w");
    for (i = 0; i < n; i++) fprintf(fdout, "%d ", v[i]);
    fprintf(fdout, "\n");
    
    fclose(fdout);
    return 0;
}