Cómo funciona
Merge Sort sigue el paradigma divide y vencerás. Parte el array por la mitad, ordena
cada mitad por separado (aplicándose a sí mismo) y después mezcla las dos mitades
ordenadas en una sola. Un tramo de un elemento ya está ordenado: es el caso base que detiene la
recursión.
En la escena, cada bandeja es una llamada a ordenar(ini, fin) y cada fila
de bandejas, un nivel de la recursión. Al dividir, las barras bajan un nivel; al mezclar, suben de una
en una al nivel de arriba: se comparan los frentes de las dos mitades y sube el menor.
Cuando una mitad se acaba, lo que queda de la otra sube sin comparar.
Paso a paso con [38, 12, 65, 27, 90, 44, 71, 9]
- 01Dividir: 8 → 4 + 4 → 2 + 2 + 2 + 2 → 8 piezas de un elemento, tres niveles más abajo.
- 02Mezclas de 2:
[12, 38], [27, 65], [44, 90] y [9, 71], con una comparación cada una.
- 03Mezclas de 4:
[12, 27, 38, 65] y [9, 44, 71, 90], con 3 comparaciones cada una.
- 04Mezcla final: 6 comparaciones. Al acabarse la mitad izquierda, el 71 y el 90 suben sin comparar →
[9, 12, 27, 38, 44, 65, 71, 90].
- ΣTotal: 16 comparaciones y 24 escrituras: 8 por nivel × 3 niveles = n·log₂ n. Bubble Sort, con el mismo array, haría 28 comparaciones. En la animación verás el orden real de la recursión: la mitad izquierda se termina entera antes de empezar la derecha.
Por qué n·log n
Cada vez que se divide, el tamaño se reduce a la mitad, así que hay unos log₂ n niveles. En cada nivel,
las mezclas escriben entre todas como mucho n elementos. Resultado: n·log₂ n, y no
depende del orden de entrada. Para n = 32 son unas 160 escrituras, frente a las cerca de 500
comparaciones que puede necesitar Bubble Sort.
Estable, pero con memoria extra
En un empate siempre sube el de la mitad izquierda, así que los iguales conservan su orden:
es estable (las letras de los repetidos nunca se cruzan). El precio es la memoria:
la mezcla necesita un espacio auxiliar de tamaño n, cuando Heap Sort o Quick Sort ordenan in situ.
Complejidad
- Mejor caso
- O(n log n)
- Caso promedio
- O(n log n)
- Peor caso
- O(n log n)
- Espacio extra
- O(n)
- Estable
- Sí
- In situ
- No