Quicksort, Mergesort y Heapsort: cuál elegir y por qué

Elegir el algoritmo de ordenación correcto puede marcar la diferencia entre una aplicación que responde en milisegundos y una que tarda segundos. Quicksort, Mergesort y Heapsort son los tres grandes del ordenamiento eficiente — cada uno con sus casos de uso ideales.

Quicksort: rápido en la práctica, impredecible en el peor caso

Quicksort tiene complejidad promedio O(n log n) pero O(n²) en el peor caso (cuando el pivote siempre cae en el extremo). En la práctica es el más rápido para datos en memoria porque aprovecha la caché del procesador. Es el algoritmo por defecto en la mayoría de librerías estándar (C qsort, Java Arrays.sort para primitivos).

Cuándo usarlo: ordenación en memoria de arrays grandes con datos aleatorios. No lo uses si necesitas estabilidad o si los datos pueden estar ya ordenados sin pivote aleatorio.

Mergesort: estable y predecible, más memoria

Mergesort garantiza O(n log n) en todos los casos. Es estable (preserva el orden relativo de elementos iguales) y predecible. El coste: necesita O(n) memoria adicional para los arrays auxiliares.

Cuándo usarlo: ordenación de listas enlazadas, cuando necesitas estabilidad, o cuando el peor caso importa (sistemas en tiempo real). Java usa Timsort (variante de Mergesort) para objetos.

Heapsort: O(n log n) garantizado con O(1) memoria extra

Heapsort combina lo mejor: complejidad garantizada O(n log n) y ordenación in-place sin memoria adicional. El problema es que accede a la memoria de forma no secuencial, lo que lo hace lento en la práctica por los fallos de caché.

Cuándo usarlo: sistemas embebidos o con memoria muy limitada donde importa el peor caso pero no tanto la velocidad real.

Tabla comparativa

Quicksort: promedio O(n log n), peor O(n²), memoria O(log n), no estable.
Mergesort: siempre O(n log n), memoria O(n), estable.
Heapsort: siempre O(n log n), memoria O(1), no estable.

Preguntas frecuentes

¿Por qué Python usa Timsort y no Quicksort?

Timsort es una variante híbrida de Mergesort e Insertionsort optimizada para datos del mundo real (con subsecuencias ya ordenadas). Es estable y garantiza O(n log n).

¿Cuándo usar Insertionsort en vez de estos tres?

Para arrays de menos de 10-20 elementos. Los algoritmos O(n log n) tienen overhead constante que los hace más lentos que O(n²) en arrays muy pequeños.