M E R G E B O I S

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

typedef struct _SNodo {
    int d;
    struct _SNodo *sig;
} SNodo;

typedef SNodo *SList;

SList SList_new(){
    return NULL;
}

SList SList_add(SList lista, int d){
    SList k = malloc(sizeof(SNodo));
    k->d = d;
    k->sig = lista;

    return k;
}

int SList_size(SList lista){
    int cont;
    SNodo *aux = lista;
    for(cont=0; aux; cont++, aux=aux->sig);

    return cont;
}

void SList_particionar(SList lista, SList *LI, SList *LD){
    int i, n = SList_size(lista);
    (*LI) = lista;

    for(i=0; i<(n-1)/2; i++)
        lista=lista->sig;
    (*LD) = lista->sig;
    lista->sig = NULL;
}


SList SList_fusionar(SList LI, SList LD){
    SList aux = malloc(sizeof(SNodo));

    if(!LI) return LD;
    if(!LD) return LI;

    SList temp, dummy = aux;

    while(LI && LD){
        dummy->sig = malloc(sizeof(SNodo));
        dummy = dummy->sig;
        if(LI->d < LD->d){
            dummy->d = LI->d;
            dummy->sig = NULL;

            temp = LI;
            LI = LI->sig;
            free(temp);
        } else {
            dummy->d = LD->d;
            dummy->sig = NULL;

            temp = LD;
            LD = LD->sig;
            free(temp);
        }
    }
    if(LI && !LD) dummy->sig = LI;
    if(!LI && LD) dummy->sig = LD;

    temp = aux;
    aux = aux->sig;
    free(temp);

    return aux;
}

SList mergesort(SList lista){
    if(SList_size(lista) <= 1) return lista;

    SList Lizq, Lder;
    SList_particionar(lista, &Lizq, &Lder);

    Lizq = mergesort(Lizq);
    Lder = mergesort(Lder);

    return SList_fusionar(Lizq, Lder);
}

void SList_print(SList lista){
    while(lista){
        printf("%d ", lista->d);
        lista = lista->sig;
    }
    puts("");
}

int main(){
    int i;
    srand(time(NULL));
    SList L = SList_new();

    for(i=0; i<15; i++)
        L = SList_add(L, rand()%1000+1);
    SList_print(L);

    L = mergesort(L);

    SList_print(L);

    return 0;
}