Ordenación (método MergeSort)

Profundizando un poco más en el tema de los algoritmos de ordenación y después de ver unos videos disponibles en la página web del MIT  he programado el algoritmo MergeSort utilizando listas enlazadas con punteros. Este algoritmo se comporta mucho mejor que el de selección cuando el número de elementos a ordenar crece. La idea que aplica este algoritmo es la de "divide y vencerás" y lo hace de modo recursivo.

struct tipo_dato {
    int num;
    struct tipo_dato *sig;
};



struct tipo_dato *mergeSort(struct tipo_dato *lista) {
    struct tipo_dato *lista1=NULL, *lista2=NULL, *listaOrd1=NULL, *listaOrd2=NULL, *listaOrd=NULL;


    if (longitud_lista(lista) <= 1) {
        return lista;
    }
    else {
        //Este es el puntero a la primera mitad de la lista.
        lista1 = lista;
        //Obtenemos la segunda parte de la lista (la segunda mitad).
        lista2 = obtener_lista2(lista);
        //Ordenamos recursivamente cada mitad del algoritmo
        listaOrd1 = mergeSort(lista1);
        listaOrd2 = mergeSort(lista2);

        //Mezclamos las dos mitades ordenadas previamente
        listaOrd = mezclar(listaOrd1, listaOrd2);

        return listaOrd;
    }
}

Para ver el código de un ejemplo de uso del algoritmo y los resultados de la ejecución podéis visitar este enlace en Codepad:
http://codepad.org/B3EOCoi8