#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
int *a;
int *b;

void read_datas(int &size)
{
     FILE *file;
     file = fopen("algsort.in","r");
     fscanf(file,"%d",&size);
     a = (int*)malloc((size+1)*sizeof(int*));
     b = (int*)malloc((size+1)*sizeof(int*));
     for (int i=1;i<=size;i++) fscanf(file,"%d",&a[i]);
}

void interclas(int left,int m,int right)

{;

int x=left;

int k=1;

int y=m+1;

while(x<=m && y<=right)

     if (a[x]<a[y])

           b[k++]=a[x++];

     else

           b[k++]=a[y++];

 

 while (x<=m)

        b[k++]=a[x++];

 while (y<=right)

        b[k++]=a[y++];

 

 int t=left;

 for (k=1;k<=(right-left)+1;k++)

        a[t++]=b[k];

}

 

void merge_sort(int left,int right)

{if (left<right)

    {int m=(left+right)/2;

     merge_sort(left,m);

     merge_sort(m+1,right);

     interclas(left,m,right);}

}

 
void print_array(int size)
{
     FILE *f = fopen("algsort.out","w");
     
     for (int i=1;i<=size;i++)
     fprintf(f,"%d ",a[i]);
     
}
 

int main(int argc, char *argv[])

{
    int size;
    read_datas(size);
    merge_sort(1,size);
    print_array(size);
    
     return 0;
    
}