MERGE_WITH_LIST

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

typedef struct list
{
    long long value;

    struct list *next;
}list;

void push(list **head, int data)
{
    list *tmp = (list*)malloc(sizeof(list));

    (*tmp).value = data;

    (*tmp).next = *head;

    (*head) = tmp;
}

long long pop(list **head)
{
    list *prev = NULL;

    long long val;

    prev = (*head);

    val = (*prev).value;

    (*head) = (*(*head)).next;

    free(prev);

    return val;
}

list *getLast(list *head)
{
    while((*head).next)
    {
        head = (*head).next;
    }
    return head;
}

void merge(list *a, list *b, list **c)
{
    list tmp;

    *c = NULL;

    if(a == NULL)
    {
        *c = b;

        return;
    }

    if(b == NULL)
    {
        *c = a;

        return;
    }

    if((*a).value < (*b).value)
    {
        *c = a;

        a = (*a).next;
    }
    else
    {
        *c = b;

        b = (*b).next;
    }

    tmp.next = *c;

    while(a&&b)
    {
        if((*a).value < (*b).value)
        {
            (*(*c)).next = a;

            a = (*a).next;
        }
        else
        {
            (*(*c)).next = b;

            b = (*b).next;
        }

        (*c) = (*(*c)).next;
    }

    if(a)
    {
        while(a)
        {
            (*(*c)).next = a;

            (*c) = (*(*c)).next;

            a = (*a).next;
        }
    }
    if(b)
    {
        while(b)
        {
            (*(*c)).next = b;

            (*c) = (*(*c)).next;

            b = (*b).next;
        }
    }

    *c = tmp.next;
}

void split(list *src, list **low, list **high)
{
    list *fast = NULL;

    list *slow = NULL;

    if(src == NULL || (*src).next == NULL)
    {
        (*low) = src;

        (*high) = NULL;

        return;
    }

    slow = src;

    fast = (*src).next;

    while(fast != NULL)
    {
        fast = (*fast).next;

        if(fast != NULL)
        {
            fast = (*fast).next;

            slow = (*slow).next;
        }
    }

    (*low) = src;

    (*high) = (*slow).next;

    (*slow).next = NULL;
}

void merGesort(list **head)
{
    list *low = NULL;

    list *high = NULL;

    if((*head == NULL) || ((*(*head)).next == NULL))
    {
        return;
    }

    split(*head, &low, &high);
    merGesort(&low);
    merGesort(&high);
    merge(low, high, head);
}

int main(void)
{
    FILE *inp, *out;

    long long current, N = 0;

    list *head = NULL;

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

    while(fscanf(inp, "%lld", &current) != EOF)
    {
        push(&head, current);

        N++;
    }

    fclose(inp);

    merGesort(&head);

    out = fopen("output.txt", "w");

    for(long long i = 0; i < N; i++)
    {
        fprintf(out, "%lld ", pop(&head));
    }

    fclose(out);

    return 0;
}