Por fin después de tanto luchar ya hallamos la respuesta de este atascamiento que algunos de nuestros usuarios de esta web presentan. Si tienes algún detalle que compartir no dejes de dejar tu comentario.
Solución:
Es razonable esperar que no pueda hacerlo mejor que O(N log N) en tiempo de ejecución.
Sin embargo, la parte interesante es investigar si puede ordenarlo en el lugar, de manera estable, su comportamiento en el peor de los casos, etc.
Simon Tatham, famoso por Putty, explica cómo ordenar una lista enlazada con la ordenación por fusión. Concluye con los siguientes comentarios:
Como cualquier algoritmo de clasificación que se precie, este tiene un tiempo de ejecución O(N log N). Debido a que se trata de Mergesort, el tiempo de ejecución en el peor de los casos sigue siendo O(N log N); no hay casos patológicos.
El requisito de almacenamiento auxiliar es pequeño y constante (es decir, algunas variables dentro de la rutina de clasificación). Gracias al comportamiento intrínsecamente diferente de las listas vinculadas de las matrices, esta implementación de Mergesort evita el costo de almacenamiento auxiliar O(N) normalmente asociado con el algoritmo.
También hay una implementación de ejemplo en C que funciona tanto para listas con enlaces simples como dobles.
Como @Jørgen Fogh menciona a continuación, la notación de O grande puede ocultar algunos factores constantes que pueden hacer que un algoritmo funcione mejor debido a la ubicación de la memoria, debido a un bajo número de elementos, etc.
Dependiendo de una serie de factores, en realidad puede ser más rápido copiar la lista a un array y luego use un Quicksort.
La razón por la que esto podría ser más rápido es que un array tiene un rendimiento de caché mucho mejor que una lista enlazada. Si los nodos de la lista están dispersos en la memoria, es posible que esté generando errores de caché por todas partes. Por otra parte, si el array es grande obtendrá errores de caché de todos modos.
Mergesort se paraleliza mejor, por lo que puede ser una mejor opción si eso es lo que desea. También es mucho más rápido si lo realiza directamente en la lista enlazada.
Dado que ambos algoritmos se ejecutan en O (n * log n), tomar una decisión informada implicaría perfilarlos en la máquina en la que le gustaría ejecutarlos.
— EDITAR
Decidí probar mi hipótesis y escribí un programa en C que medía el tiempo (usando clock()) tomado para ordenar una lista enlazada de enteros. Probé con una lista enlazada donde cada nodo se asignó con malloc() y una lista enlazada donde los nodos se dispusieron linealmente en un array, por lo que el rendimiento de la memoria caché sería mejor. Los comparé con el qsort incorporado, que incluía copiar todo, desde una lista fragmentada a un array y copiando el resultado de nuevo. Cada algoritmo se ejecutó en los mismos 10 conjuntos de datos y se promediaron los resultados.
Estos son los resultados:
norte = 1000:
Lista fragmentada con ordenación por fusión: 0.000000 segundos
Matriz con qsort: 0.000000 segundos
Lista empaquetada con clasificación por fusión: 0.000000 segundos
N = 100000:
Lista fragmentada con clasificación por fusión: 0.039000 segundos
Matriz con qsort: 0.025000 segundos
Lista empaquetada con clasificación por fusión: 0.009000 segundos
N = 1000000:
Lista fragmentada con ordenación por fusión: 1.162000 segundos
Matriz con qsort: 0.420000 segundos
Lista empaquetada con clasificación por fusión: 0.112000 segundos
N = 100000000:
Lista fragmentada con ordenación por fusión: 364.797000 segundos
Matriz con qsort: 61.166000 segundos
Lista empaquetada con clasificación por combinación: 16.525000 segundos
Conclusión:
Al menos en mi máquina, copiando en un array Vale la pena mejorar el rendimiento de la memoria caché, ya que rara vez se tiene una lista de enlaces completa en la vida real. Cabe señalar que mi máquina tiene un Phenom II de 2,8 GHz, pero solo 0,6 GHz de RAM, por lo que el caché es muy importante.
Este es un pequeño y agradable artículo sobre este tema. Su conclusión empírica es que Treesort es el mejor, seguido de Quicksort y Mergesort. La clasificación por sedimentos, la clasificación por burbujas y la clasificación por selección funcionan muy mal.
UN ESTUDIO COMPARATIVO DE ALGORITMOS DE CLASIFICACIÓN DE LISTAS ENLAZADAS por Ching-Kuang Shene
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.9981
Comentarios y valoraciones
No se te olvide recomendar este enunciado si te valió la pena.