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

void merge(double *a, int sizeA, double *b, int sizeB, double *c);
void sort(double *a, int n);
void splitMerge(double *b, int beg, int end, double *a);
void copy(double *A, double *B, int N);

int main(void) {
    FILE *IN, *OUT;
    double x, *A;
    int NA = 0, i;

    /* Count numbers in input.txt */
    IN = fopen("input.txt", "r");
    if (IN == NULL) {
        printf("File input.txt not opened\n");
        return -1;
    }
    while (fscanf(IN, "%lf", &x) == 1)
        ++NA;
    fclose(IN);
    if (NA <= 0) {
        printf("File ina.txt empty\n");
        return -1;
    }
    /* Allocate memory for array A */
    A = (double*)malloc(NA * sizeof(A[0]));
    if (A == NULL) {
        printf("Memory not allocated\n");
        return -1;
    }
    /* Read array A from input.txt */
    IN = fopen("input.txt", "r");
    if (IN == NULL) {
        printf("File ina.txt not opened\n");
        return -1;
    }
    for (i = 0; i < NA; i++) {
        if (fscanf(IN, "%lf", &A[i]) != 1) {
            printf("Not enough numbers\n");
            return -1;
        }
    }
    fclose(IN);

    sort(A, NA);

    /* Create file output.txt */
    OUT = fopen("output.txt", "w");
    if (OUT == NULL) {
        free(A);
        printf("File output.txt not opened\n");
        return -1;
    }

    /* Output array A to output.txt */
    for (i = 0; i < NA; i++) {
        fprintf(OUT, "%lf ", A[i]);
    }
    fclose(OUT);
    free(A);
    return 0;
}

void merge(double *a, int sizeA, double *b, int sizeB, double *c) {
    int sizeC = sizeA + sizeB;
    int i = 0, j = 0, k;
    for (k = 0; k < sizeC; k++) {
        if ((i < sizeA) && ((j >= sizeB) || (a[i] < b[j]))) {
            c[k] = a[i++];
        } else {
            c[k] = b[j++];
        }
    }
}

void sort(double *a, int n) {
    double *b = (double*)malloc(n * sizeof(double));
    copy(a, b, n);
    splitMerge(b, 0, n, a);
    free(b);
}

void splitMerge(double *b, int beg, int end, double *a) {
    int mid;
    if ((end - beg) >= 2) {
        mid = (beg + end) / 2;
        splitMerge(a, beg, mid, b);
        splitMerge(a, mid, end, b);
        merge(&b[beg], mid - beg, &b[mid], end - mid, &a[beg]);
    }
}

void copy(double *A, double *B, int N) {
    double *endA = &A[N];
    while (A < endA)
        *(B++) = *(A++);
}