Merge_Sort_Linked_List

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

typedef struct nodo{
  int valor;
  struct nodo* ptrSig;
}TNodo;

int lista_vacia(TNodo *);
void inserta_inicio(TNodo **, int);

void imprime_lista(TNodo *);
void libera_lista(TNodo *);
TNodo* Merge(TNodo* , TNodo* );
void Split(TNodo *,TNodo ** ,TNodo**);
void MergeSort(TNodo **);

void inserta_inicio(TNodo **ptrListaSE, int valor){
    TNodo *ptrNuevo;
    ptrNuevo = (TNodo*)malloc(sizeof(TNodo));
    ptrNuevo->valor = valor;
    ptrNuevo->ptrSig = *ptrListaSE;
    *ptrListaSE = ptrNuevo;
}

int lista_vacia(TNodo * ptrListaSE){
    return ptrListaSE==NULL;
}

void imprime_lista(TNodo * ptrListaSE){
    while (ptrListaSE != NULL){
        /*printf(" %d ", (*ptrListaSE).valor);*/
        printf(" %d ", ptrListaSE->valor);
        ptrListaSE = ptrListaSE->ptrSig;
    }
    printf("NULL\n");
}

void libera_lista(TNodo * ptrListaSE){
    TNodo * ptrEliminar;
    while (ptrListaSE != NULL){
        ptrEliminar = ptrListaSE;
        ptrListaSE = ptrListaSE->ptrSig;
        free(ptrEliminar);
    }
}

/* function to swap data of two nodes a and b*/
void swap(TNodo *a, TNodo *b)
{
    int temp = a->valor;
    a->valor = b->valor;
    b->valor = temp;
}


/* See http://geeksforgeeks.org/?p=3622 for details of this
   function */
TNodo* Merge(TNodo* a, TNodo* b)
{
  TNodo* result = NULL;

  /* Base cases */
  if (a == NULL)
     return(b);
  else if (b==NULL)
     return(a);

  /* Pick either a or b, and recur */
 // TNodo * head;
  /*head=result;
  while((a!=NULL) || (b!=NULL)){
      if(a->valor <=b->valor ){
          result->valor=a->valor;
          result=result->ptrSig;

      }else{
          result->valor=b->valor;
          result=result->ptrSig;
      }
  }*/

  if (a->valor <= b->valor)
  {
     result = a;
     result->ptrSig = Merge(a->ptrSig, b);
  }
  else
  {
     result = b;
     result->ptrSig = Merge(a, b->ptrSig);
  }

  /*
  if (a!=NULL){
      while(a!=NULL){
          result->valor=a->valor;
          result=result->ptrSig;
          a=a->ptrSig;
      }
  }
  if (b!=NULL){
      while(b!=NULL){
          result->valor=b->valor;
          result=result->ptrSig;
          b=b->ptrSig;
      }
  }*/
  return(result);
}
/* UTILITY FUNCTIONS */
/* Split the nodes of the given list into front and back halves,
     and return the two lists using the reference parameters.
     If the length is odd, the extra node should go in the front list.
     Uses the fast/slow pointer strategy.  */
void Split(TNodo* source, TNodo** frontRef, TNodo** backRef){
    {
  TNodo* fast;
  TNodo* slow;
  if (source==NULL || source->ptrSig==NULL)
  {
    /* length < 2 cases */
    *frontRef = source;
    *backRef = NULL;
  }
  else
  {
    slow = source;
    fast = source->ptrSig;

    /* Advance 'fast' two nodes, and advance 'slow' one node */
    while (fast != NULL)
    {
      fast = fast->ptrSig;
      if (fast != NULL)
      {
        slow = slow->ptrSig;
        fast = fast->ptrSig;
      }
    }

    /* 'slow' is before the midpoint in the list, so split it in two
      at that point. */
    *frontRef = source;
    *backRef = slow->ptrSig;
    slow->ptrSig = NULL;
  }
}
}
void Mergesort(TNodo** ptrListaSE){
    //Creo un nodo que apunte a la cabeza de la lista
    TNodo* head=*ptrListaSE;
    TNodo *a;
    TNodo*b;
    /*Caso base , longitud 0 o 1*/
    if ((head==NULL)|| (head->ptrSig == NULL)) return;
    /*Parto head en 2 sublistas a y b*/
    Split(head,&a,&b);
    /*Recursivamente ordeno las sublistas*/
    Mergesort(&a);
    Mergesort(&b);

    /*la respuesta es unir las 2 listas ordenadas*/
     * ptrListaSE= Merge(a,b);

}
int main(int argc, char** argv) {
    TNodo * ptrListaSE = NULL;
    TNodo * ptrUltimo = NULL;
    inserta_inicio(&ptrListaSE, 19);
    inserta_inicio(&ptrListaSE, 15);
    inserta_inicio(&ptrListaSE, 17);
    inserta_inicio(&ptrListaSE, 20);
    Mergesort(&ptrListaSE);
    imprime_lista(ptrListaSE);
    libera_lista(ptrListaSE);
    return (EXIT_SUCCESS);
}