//Сортировка слиянием и вставками, непр. ответ на 6 тесте, там 0 вначале должен быть, а у меня в конце

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

int *array;

void merge(unsigned long k, unsigned long l, unsigned long m, int *array)
{
   int *T=(int*)malloc((m-k+1)*sizeof(int));
   int i=k;
   int j=l+1;
   int h;
   for(h=0;h<m-k+1;h++){
        if ((j<=m) && ((i==l+1) || (array[i]>array[j]))){
            T[h]=array[j];
            j++;
        }
        else{
            T[h]=array[i];
            i++;
        }
   }
   for(i=k, j=0;i<m;i++, j++)
        array[i]=T[j];
    free(T);
}

void insertionsort(int nel, int *array)
{
    int i, temp, pred;
    for (i=1; i<nel; i++){
        temp=array[i];
        for (pred=i-1; pred>=0 && (abs(array[pred])>abs(temp));pred--){
            array[pred+1]=array[pred];
            array[pred]=temp;
        }
    }
}

void mergesort(int low, int high, int nel, int *array)
{
    int med;
    if (nel<=5){
        insertionsort(nel, array);
        return;
    }
    if (low<high)
        med=(int)(low+high)/2;
    mergesort(low, med, med-low+1, array);
    mergesort(med+1, high, high-med, array);
    merge(low, med, high, array);
}

int main()
{
    int i, nel;
    scanf("%d", &nel);
    array = (int*)malloc(nel*sizeof(int));
    for (i=0;i<nel;i++)
        scanf("%d", &array[i]);
    mergesort(0, nel-1, nel, array);
    for (i=0;i<nel;i++)
        printf("%d ", array[i]);
    printf("\n");
    free(array);
    return 0;
}