// Merge Sort
#include <stdio.h>

#define NX 500010

int N, A[NX], B[NX];

void merge_sort(int l, int r) {
    int m = (l + r) >> 1, i, j, k;

    if( l == r ) return;

    merge_sort( l, m );
    merge_sort( m + 1, r );

    for( i = l, j = m+1, k = l; i <= m || j <= r; )
        if( j > r || (i <= m && A[i] < A[j]) )
            B[ k++ ] = A[ i++ ];
        else
            B[ k++ ] = A[ j++ ];
    for( k = l; k <= r; k++ )
        A[k] = B[k];
}

int main() {
    int i;

    freopen( "algsort.in", "r", stdin );
    freopen( "algsort.out", "w", stdout );

    scanf( "%d", &N );
    for( i = 1; i <= N; i++ )
        scanf( "%d", A+i );

    merge_sort( 1, N );

    for( i = 1; i <= N; i++ )
        printf( "%d ", A[i] );

    return 0;
}
/*
// Heapsort
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

vector< int > V;

int main() {
    int N, x, i;

    ifstream fi( "algsort.in" );
    ofstream fo( "algsort.out" );

    fi >> N;
    for( i = 0; i < N; i++ ) {
        fi >> x;
        V.push_back( x );
    }

    make_heap( V.begin(), V.end() );
    sort_heap( V.begin(), V.end() );

    for( i = 0; i < N; i++ )
        fo << V[i] << ' ';

    fi.close(); fo.close();
    return 0;
}
*/
/*
//  implementata o varianta naiva de Quicksort in C
#include <stdio.h>
#include <stdlib.h>

#define NX 500010

int N, v[ NX ];

int cmp( const void*x, const void *y ) {
    return *(int*)x - *(int*)y;
}

int main() {
    int i;

    freopen( "algsort.in", "r", stdin );
    freopen( "algsort.out", "w", stdout );

    scanf( "%d", &N );

    for( i = 0; i < N; i++ )
        scanf( "%d", v+i );

    qsort( v, N, sizeof( v[0] ), cmp );

    for( i = 0; i < N; i++ )
        printf( "%d ", v[i] );

    return 0;
}
*/
/*
// Introsort
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

vector< int > V;

int main() {
    int i, x, N;

    freopen( "algsort.in", "r", stdin );
    freopen( "algsort.out", "w", stdout );

    scanf( "%d", &N );

    for( i = 1; i <= N; i++ ) {
        scanf( "%d", &x );
        V.push_back( x );
    }

    sort( V.begin(), V.end() );

    for( i = 0; i < N; i++ )
        printf( "%d ", V[i] );

    return 0;
}
*/