#include <stdio.h>
#include <malloc.h>

struct list{
    int value;
    struct list *next;
};

void init(struct list **ptrptr)
{
    *ptrptr = NULL;
}

void suf_insert(struct list **ptrptr, int value)
{
    while (*ptrptr != NULL)
        ptrptr = &((*ptrptr)->next);
    *ptrptr = (struct list *)malloc(sizeof(struct list));
    if(*ptrptr!=NULL){
        (*ptrptr)->value = value;
        (*ptrptr)->next = NULL;
        return;
    }
    else
        return;
}

void visit(struct list *ptr)
{
    printf("\nList: ");
    while (ptr != NULL)
    {
        printf("%d ", ptr->value);
        ptr = ptr->next;
    }
}

void moveElm(struct list ** ppList, struct list ** elm) {

    (*elm)->next = NULL;
    if (*ppList == NULL)
        *ppList = *elm;
    else {
        while ((*ppList)->next != NULL)
            ppList = &(*ppList)->next;
        (*ppList)->next = *elm;
    }

}

void merge(struct list **ppFirstHalf, struct list **ppSecondHalf) {

    struct list ** ppFirstHalfTmp = ppFirstHalf;
    struct list ** ppSecondHalfTmp = ppSecondHalf;
    struct list * returnList = NULL;

    while (*ppFirstHalfTmp != NULL || *ppSecondHalfTmp != NULL) {

        if (*ppFirstHalfTmp == NULL) {

            struct list *tmp = *ppSecondHalfTmp;
            *ppSecondHalfTmp = (*ppSecondHalfTmp)->next;
            moveElm(&returnList, &tmp);

        } else if (*ppSecondHalfTmp == NULL) {

            struct list *tmp = *ppFirstHalfTmp;
            *ppFirstHalfTmp = (*ppFirstHalfTmp)->next;
            moveElm(&returnList, &tmp);

        } else if ((*ppFirstHalfTmp)->value < (*ppSecondHalfTmp)->value) {

            struct list *tmp = *ppFirstHalfTmp;
            *ppFirstHalfTmp = (*ppFirstHalfTmp)->next;
            moveElm(&returnList, &tmp);

        } else {

            struct list *tmp = *ppSecondHalfTmp;
            *ppSecondHalfTmp = (*ppSecondHalfTmp)->next;
            moveElm(&returnList, &tmp);

        }

    }

    *ppFirstHalf = returnList;

}

void merge_Sort(struct list **ptrptr, int size) {
    if (size > 1) {

        int half = size / 2;
        struct list ** pptmp = ptrptr;
        struct list ** ppHalfList;

        for (int i = 0;i < half;i++) {
            pptmp = &(*pptmp)->next;
        }
        struct list * tmpEl = malloc(sizeof(struct list));
        tmpEl->next = (*pptmp)->next;
        tmpEl->value = (*pptmp)->value;
        ppHalfList = &tmpEl; //Seconda meta

        (*pptmp) = NULL; //ul. el. Prima meta


        merge_Sort(ptrptr, half);
        merge_Sort(ppHalfList, size - half);
        merge(ptrptr, ppHalfList);

    }
}

void mergeSort(struct list **ptrptr) {
    int size = 0;

    struct list ** pptmp = ptrptr;

    while (*pptmp != NULL) {
        pptmp = &(*pptmp)->next;
        size++;
    }
    merge_Sort(ptrptr, size);
}

int main() {
    struct list * lista;
    init(&lista);

    suf_insert(&lista, 7);
    suf_insert(&lista, 9);
    suf_insert(&lista, 0);
    suf_insert(&lista, 3);
    suf_insert(&lista, 1);
    suf_insert(&lista, 1);
    suf_insert(&lista, 5);

    visit(lista);

    mergeSort(&lista);

    visit(lista);

    printf("\nFine");
    return 0;
}