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

#define EPS 1E-6

int compare_newdouble(const void *left, const void *right);
int compare_newdouble(const void *left, const void *right)
{
    double *p = (double*)left;
    double *q = (double*)right;

    if(fabs(fabs(*p) - fabs(*q)) < EPS)
    {
        return 0;
    }

    if(fabs(*p) > fabs(*q))
    {
        return 1;
    }

    return -1;
}

void arrswap(void *base, void *add);
void arrswap(void *base, void *add)
{
    void *c;
    c=base;
    base=add;
    add=c;
}

void merge(void *base, void *add, size_t mid, size_t n, size_t size, int (*compar)(const void *, const void *));
void merge(void *base, void *add, size_t mid, size_t n, size_t size, int (*compar)(const void *, const void *))
{
    size_t l = 0, r = 0, a = 0;

    while(l < mid && r < (n-mid))
    {
        if((*compar)((char*)base+size*l, (char*)base+size*mid+size*r) == -1)
        {
            memcpy(((char*)add+size*a), ((char*)base+size*l), size); // putting the memory from left to add
            a++;
            l++;
        }
        else
        {
            memcpy(((char*)add+size*a), ((char*)base+size*mid+size*r), size); // putting the memory from right to add
            a++;
            r++;
        }
    }

    if(l < mid)
    {
        memcpy(((char*)add+size*a), ((char*)base+size*l), size*(mid - l));
    }

    if(r < (n-mid))
    {
        memcpy(((char*)add+size*a), ((char*)base+size*mid+size*r), size*(n-mid - r));
    }
}

void mergesort(void *base, size_t n, size_t size, int (*compar)(const void *, const void *));
void mergesort(void *base, size_t n, size_t size, int (*compar)(const void *, const void *))
{
    size_t mid = n/2;
    void* add=malloc(size*n);

    if(n < 2) // array length = 1
    {
        return;
    }

    mergesort(base, mid, size, compar); //left array
    mergesort((char*)base+size*mid, n-mid, size, compar); //right array

    merge(base, add, n/2, n, size, compar);

    arrswap(base, add);

    memcpy(base, add, size*n);

    free(add);
}

int main(void)
{
    FILE *inp;
    FILE *outp;
    int n, i;
    double *arr;

    inp=fopen("input.txt", "r");
    outp=fopen("output.txt", "w");

    if(inp==NULL)
    {
        perror("Error. File input.txt cannot be found");
        return -1;
    }

    fscanf(inp, "%d ", &n);
    arr=malloc(sizeof(double)*n);

    for(i = 0; i < n; i++)
    {
        fscanf(inp, "%lf ", &arr[i]);
    }

    mergesort(arr, n, sizeof(double), &compare_newdouble);

    for(i = 0; i < n; i++)
    {
        fprintf(outp, "%lf ", arr[i]);
    }

    printf("Done. \n");

    fclose(inp);
    fclose(outp);
    free(arr);

    return 0;
}