merge_sort

#include <iostream>

using namespace std;

int a[1000000], c[1000000], n;

void merge( int u, int v, int w ){
    int i,j,k;

    for( i=u, j=v+1, k=0; i<=v && j<=w; k++){
        if( a[i] <= a[j] ) c[k] = a[i++];
        else c[k] = a[j++];
    }

    if( i>v ) for( i=j; i<=w; i++) c[k++] = a[i];
    else for( j=i; j<=v; j++) c[k++] = a[j];

    for ( i=0; i<k; i++ ) a[ u+i ] = c[i];
}


void  merge_sort( int p, int q ){
    if( p==q ) return;
    merge_sort( p, (q+p)/2 );
    merge_sort( (q+p)/2+1, q );
    merge( p, (q+p)/2, q);
}


void main(){
    cin >> n;
    for( int i=0; i<n; i++ ) cin >> a[i];

    if(n!=1) merge_sort(0, n);

    for( int i=0; i<n; i++ ) cout << c[i]<< " ";
}