Merge sort
Parte a la mitad, ordena cada mitad, mezcla.
El primer sort O(n log n) — sin caso malo.
La mezcla es el truco
- Dos tramos ordenados → un tramo ordenado en O(n) (dos dedos, toma el menor)
- Haz eso en cada nivel de una partición a la mitad
- log n niveles × O(n) por nivel = O(n log n)
- Estable (los empates se van a la izquierda); necesita O(n) de memoria auxiliar
Mira los tramos mezclarse y crecer
12 tramos de longitud 1 → 2 → 4 → 8 → ordenado.
Cada tramo verde es una mezcla.
O(n log n), garantizado
T(n)=2T(n/2)+O(n)=O(nlogn)
No hay entrada adversaria — la partición no depende de los datos.
El trade
- Merge sort: O(n log n) garantizado, estable, secuencial — pero O(n) de memoria
- Ideal para: entradas impredecibles, datos externos, listas ligadas
- vs. quicksort (el que sigue): in-place, más rápido, pero peor caso O(n²)
Conclusión
Cambias memoria por una garantía. El sort detrás de todo sort estable de librería
y de todo "ordena un archivo que no cabe en memoria". Sigue: quicksort.