#include <stdio.h>
#include <stdbool.h>
#define MAX 500000

void merge_sort(long *array, long n);
void merge(long *array, long n, long mij);

void merge_sort(long *array, long n)
{
    long mij;
    if(n < 2){
        return;
    }

    mij = n / 2;
    merge_sort(array,mij);
    merge_sort(&array[mij], n - mij);
    merge(array, n, mij);
}

void merge(long *array, long n, long mij)
{
    long l,r,k,array_aux[MAX];

    l=0;
    r=mij;

    for( k = 0; k < n; k++){
        if(r == n){
            array_aux[k] = array[l];
            l++;
        }
        else{
            if(l == mij){
                array_aux[k] = array[r];
                r++;
            }
            else{
                if(array[r] <= array[l]){
                    array_aux[k] = array[r];
                    r++;
                }
                else{
                    array_aux[k] = array[l];
                    l++;
                }
            }
        }
    }
    for(k = 0; k < n; k++){
        array[k] = array_aux[k];
    }
}

int main()
{
    long array[MAX],n=0,i;

    FILE *in=fopen("algsort.in","r");
    fscanf(in,"%d",&n);
    for( i=0;i<n;i++ ){
        fscanf(in,"%ld",&array[i] );
    }
    fclose(in);

    merge_sort(array, n);

    FILE *out=fopen("algsort.out","w");
    for( i=0;i<n;i++ ){
        fprintf(out,"%ld ",array[i] );
    }
    fclose(out);

    return 0;
}