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

#define NMAX 500000

int vec[NMAX + 1], vec_aux[NMAX + 1];

void merge( int vec[], int left, int mid, int right ) {
  int ind1, ind2, poz, ind;

  ind1 = poz = left;
  ind2 = mid + 1;

  while ( ind1 <= mid && ind2 <= right ) {
    if ( vec[ind1] <= vec[ind2] )
      vec_aux[poz++] = vec[ind1++];
    else
      vec_aux[poz++] = vec[ind2++];
  }

  while ( ind1 <= mid )
    vec_aux[poz++] = vec[ind1++];

  while ( ind2 <= right )
    vec_aux[poz++] = vec[ind2++];

  for ( ind = left; ind <= right; ind++ )
    vec[ind] = vec_aux[ind];
}

void mergesort( int vec[], int left, int right ) {
  if ( left == right )
    return;

  int mid = ( left + right ) / 2;
  mergesort( vec, left, mid );
  mergesort( vec, mid + 1, right );

  merge( vec, left, mid, right );
}

int main()
{
    FILE *fin, *fout;
    int num_n, ind;

    fin = fopen( "algsort.in", "r" );
    fscanf( fin, "%d", &num_n );

    for ( ind = 0; ind < num_n; ind++ )
      fscanf( fin, "%d", &vec[ind] );
    fclose( fin );

    mergesort( vec, 0, num_n - 1 );

    fout = fopen( "algsort.out", "w" );
    for ( ind = 0; ind < num_n; ind++ )
      fprintf( fout, "%d ", vec[ind] );
    fclose( fout );
    return 0;
}