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

void interclasare (int *v, int s, int d) {
    int *p = (int*)malloc(((d-s)+1)*sizeof(int));
    int n = 0,i,j;
    i = s;
    j = (s+d)/2+1;
    while (i<=(s+d)/2 && j<=d) {
        if (v[i]<=v[j]) {
            p[n] = v[i];
            if (v[i] == v[j]) {
                j++;
                p[n+1] = v[i];
                n++;
            }
            i++;
            n++;
            continue;
        }
        if (v[j]<v[i]) {
            p[n] = v[j];
            j++;
            n++;
        }
    }
    while (i<=(s+d)/2) {
        p[n] = v[i];
        i++;
        n++;
    }
    while (j<=d) {
        p[n] = v[j];
        j++;
        n++;
    }
    for (i=s,n=0;i<=d;i++,n++)
        v[i] = p[n];
}

void merge(int *v, int s, int d) {
    if (d == s) return;
    merge(v,s,(s+d)/2);
    merge(v,(s+d)/2+1,d);
    interclasare(v,s,d);
}

int main()
{
    int *v, n,i;
    FILE *f;
    f = fopen("algsort.in","r");
    fscanf(f,"%d",&n);
    v = (int*)malloc(n*sizeof(int));
    for (i=0;i<n;i++) fscanf(f,"%d",&v[i]);
    fclose(f);
    merge(v,0,n-1);
    f = fopen("algsort.out","w");
    for (i=0;i<n;i++) fprintf(f,"%d ",v[i]);
    fclose(f);
    return 0;
}