Cómo funciona merge sort

De uno en uno es lento

El método anterior tenía la ventaja de ser simple: comparar vecinos y mandar atrás al mayor.
Pero cuando la fila crece, hay demasiado que comparar.
Si se duplican las cartas, las comparaciones se multiplican por cuatro. Con cuatro es rápido, pero con treinta y dos parece no terminar nunca.

Duplica la fila. Doble de largo → cuatro veces más comparaciones.

Las barras suben de forma alarmante.
Cuanto más larga la fila, peor es la lentitud.
El problema es tratar la fila entera como un solo bloque y comparar hasta el final.
Entonces, ¿y si partimos el bloque?

Partir por la mitad

En lugar de manejar la fila larga entera, pártela por la mitad.
Parte cada mitad otra vez, y otra, y al final solo quedan casillas sueltas.
Y una casilla sola ya está ordenada, porque está sola y no tiene con quién compararse.

Sigue partiendo un grupo por la mitad. 8 → 4+4 → 2+2+2+2 → una casilla cada uno.

¿Termina todo con partir?
No. Lo que se parte hay que volver a juntarlo en una fila: se emparejan las casillas sueltas y se combinan, y luego se combinan otra vez esos grupos.
Y combinar dos grupos ya ordenados resulta sorprendentemente fácil.

Combinar dos grupos ordenados

El secreto para combinar dos grupos ordenados en una fila es mirar solo el principio.
Se compara la primera casilla de cada grupo y se deja caer la menor en el resultado. La siguiente casilla ocupa su lugar y se vuelven a comparar las primeras.
Se van encajando de una en una, como una cremallera que se cierra.

Compara el principio de los dos grupos y deja caer el menor. Se combina casilla a casilla, como una cremallera.

¿No es curioso? Comparar toda la fila revuelta era lento, pero combinar dos grupos ya ordenados es rápido, porque solo hay que mirar el principio.
Partir crea trozos pequeños y ordenados, y al combinarlos paso a paso pronto se obtiene una fila completa.

Por qué es rápido: el número de niveles

¿Por qué esto es más rápido?
Como se parte por la mitad, no hay muchos niveles de partición. Aunque la fila se duplique, los niveles solo aumentan en uno.
Combinar un nivel cuesta más o menos lo que mide la fila, así que el coste total es el número de niveles por la longitud de la fila.
Eso crece mucho más despacio que comparar de uno en uno (longitud por longitud).

Despliega los niveles y cambia la longitud de la fila. Niveles x un nivel = crece más despacio que de uno en uno.

La fórmula exacta la aprenderás más adelante.
Por ahora basta con quedarse con la idea: al partir por la mitad, los niveles crecen despacio y cada nivel se combina con poco esfuerzo, así que todo va más rápido.
Este solo movimiento de partir y combinar cambia la velocidad por completo.

Resumen

Hilado en una sola idea, queda así.
Ordenar comparando de uno en uno se vuelve más lento cuanto más larga es la fila.
Por eso se parte la fila por la mitad y se sigue partiendo hasta tener casillas sueltas, que ya son trozos ordenados.
Al combinar esos pares ordenados como una cremallera, solo hay que combinar tantas veces como niveles hay, y toda la fila se ordena mucho más rápido.
Partir y combinar: ese es el corazón de una ordenación más lista.

Pulsa los cuatro pasos uno tras otro y sigue una vuelta completa. Partir → casilla suelta → combinar → solo tantos niveles como hagan falta = rápido.

Aquí siempre partimos tranquilamente por la mitad.
Pero hay un primo que elige el punto de división de otra manera: en lugar de la mitad, toma una casilla como pivote y divide el resto en menores y mayores.
Cómo elegir ese pivote es una historia para más adelante.
Hoy quédate solo con esto: si partes por la mitad y combinas, todo va más rápido.