ordenar: bajar partiendo, subir mezclando

El ordenamiento por mezcla, dibujado completo. Parta la lista nivel por nivel hasta el caso base, súbala mezclando, y mire cuánto trabajo hace cada piso del árbol: el patrón que aparece explica el famoso n·lg n.

1. Antes de partir, prediga

Tamaño:

Partiendo a la mitad una y otra vez hasta llegar a listas de un elemento, ¿cuántos niveles (filas) aparecen, contando la lista completa?

2. Bajar partiendo

3. Subir mezclando

Cada clic mezcla las listas de un nivel, por parejas, usando el mezclar del ejercicio anterior. La tabla lleva la cuenta del trabajo por nivel.

Nivel de mezcla	Mezclas	Tamaño resultante	Elementos movidos

4. El patrón

Mire la columna «Elementos movidos» de la tabla.

¿Cuánto trabajo hace cada nivel de mezcla?

¿Y cuántos niveles de mezcla hay?

5. La generalización

Cada nivel de mezcla mueve n elementos y hay lg n niveles (más el nivel original): el total es c·n·(lg n + 1), es decir Θ(n·lg n). La recurrencia T(n) = 2·T(n/2) + Θ(n) es este dibujo escrito en una línea: dos mitades, más el costo n de mezclar el nivel.

n	n² (burbuja)	n·(lg n + 1) (mezcla)
8	64	32
1 024	1 048 576	11 264
1 000 000	≈ 10¹²	≈ 2 × 10⁷

Con un millón de datos: un billón de operaciones contra veinte millones. Partir el problema pagó, porque la mezcla aprovecha el trabajo que las dos mitades ya hicieron.