Este capítulo resume las diferencias clave entre los tres ordenamientos eficientes que vimos: MergeSort, QuickSort y HeapSort. La decisión depende de complejidad, estabilidad, memoria y las características de los datos y del hardware.
6.1 Complejidad temporal
- MergeSort:
O(n log n) en todos los casos, con un patrón de trabajo regular (mezclas lineales en cada nivel del árbol).
- QuickSort: promedio
O(n log n); peor caso O(n^2) si el pivote se degrada, aunque la mediana de tres o pivote aleatorio reducen esa probabilidad.
- HeapSort:
O(n log n) garantizado; cada extracción cuesta log n y se realizan n extracciones.
6.2 Requerimientos de memoria
- MergeSort: requiere un buffer auxiliar de
O(n); es el costo de su estabilidad y del esquema de mezcla.
- QuickSort: in-place; pila de llamadas
O(log n) en promedio, hasta O(n) si las particiones son muy desbalanceadas.
- HeapSort: in-place con
O(1) espacio extra; no depende de la pila para la fase principal.
6.3 Estabilidad del algoritmo
- MergeSort: estable si la mezcla respeta el orden de iguales.
- QuickSort: no estable en sus versiones comunes.
- HeapSort: no estable debido a los intercambios con la raíz.
6.4 Recursión vs iteración
- MergeSort: recursivo (top-down) o iterativo (bottom-up); recursión aporta claridad.
- QuickSort: recursivo; puede hibridarse con iteración en tramos pequeños.
- HeapSort: iterativo; no depende de la pila y su flujo de control es constante.
6.5 Rendimiento en arrays casi ordenados
- MergeSort: consistente y estable; aprovecha runs existentes.
- QuickSort: puede ser rápido si el pivote es bueno; con pivote fijo puede degradar e incrementar comparaciones innecesarias.
- HeapSort: no capitaliza el pre-orden; su costo se mantiene cercano a su peor caso.
6.6 Rendimiento en arrays muy grandes
- MergeSort: predecible, pero requiere memoria adicional que puede ser un factor limitante.
- QuickSort: excelente uso de caché y constantes bajas; vigilar el peor caso o hibridar con HeapSort (introsort).
- HeapSort: garantizado y con memoria
O(1); los accesos dispersos pueden penalizar caché en algunos escenarios.
6.7 Rendimiento en hardware limitado
- MergeSort: limitado por el buffer; puede no ser ideal si la RAM es escasa.
- QuickSort: cuidado con la profundidad de pila en dispositivos con stack reducido; conviene pivote aleatorio y límite de recursión.
- HeapSort: buena opción cuando la memoria es crítica y se necesita tiempo acotado en todas las entradas.
6.8 Tabla comparativa
| Algoritmo |
Mejor caso |
Promedio |
Peor caso |
Espacio extra |
Estabilidad |
| MergeSort |
O(n log n) |
O(n log n) |
O(n log n) |
O(n) |
Sí |
| QuickSort |
O(n log n) |
O(n log n) |
O(n^2) |
O(1) + pila |
No |
| HeapSort |
O(n log n) |
O(n log n) |
O(n log n) |
O(1) |
No |