Ordenar de forma más lista

Una por una es lento

La forma de la vez pasada era simple y bonita.
Compara vecinos, el mayor atrás.
Pero cuando la fila se alarga,
hay demasiado que comparar.
El doble de cartas,
y las comparaciones saltan al cuádruple.
Cuatro es rápido,
pero treinta y dos es larguísimo.

Prueba a duplicar la fila. (El largo se duplica → las comparaciones saltan al cuádruple)

La barra sube de forma alarmante.
Cuanto más larga la fila,
peor se pone la lentitud.
El problema es tratar
toda la fila como un solo bulto
y comparar hasta el final.
Entonces, ¿y si
rompemos el bulto?

Pártelo por la mitad

No manejes la fila larga entera.
Pártela por la mitad.
Esa mitad por la mitad otra vez,
y esa mitad también.
Sigue partiendo,
y al final solo quedan sueltos.
Pero un suelto
ya está ordenado.
Solo, no hay nada que comparar.

Sigue partiendo un grupo a la mitad. (8 → 4+4 → 2+2+2+2 → sueltos)

¿Partir es todo el trabajo?
No, las piezas partidas
deben volver a unirse para hacer una fila.
Empareja los sueltos
y fusiónalos de dos en dos,
luego fusiona esos otra vez.
Y fusionar dos piezas ordenadas
resulta sorprendentemente fácil.
Veámoslo a continuación.

Fusiona dos ordenados

Tenemos dos grupos ordenados.
Para fusionarlos en una fila,
el truco es mirar solo los frentes.
Compara la primera carta de cada uno,
suelta la menor al resultado.
La siguiente carta llena ese hueco,
y comparas los frentes de nuevo.
Como al cerrar un cierre,
encajan de a una muesca a la vez.

Compara los frentes de los dos grupos, suelta el menor. (Fusiona de a una muesca, como un cierre)

¿No es ingenioso?
Comparar todo un revoltijo era lento,
pero fusionar dos ya ordenados
es rápido, pues solo miras los frentes.
Gracias a partir,
obtenemos piezas pequeñas y ordenadas,
y al fusionarlas poco a poco
se vuelve una fila entera sin que te des cuenta.

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

¿Por qué es más rápido?
Como partimos a la mitad,
no hay muchas capas de división.
Duplica la fila,
y las capas crecen solo en una.
Y fusionar una capa
cuesta más o menos el largo de la fila.
Así que el costo total es
capas por largo de la fila.
Eso crece mucho más lento
que uno por uno (largo por largo).

Despliega las capas y cambia el largo. (Capas x por capa crece más lento que uno por uno)

La fórmula exacta viene después.
Por ahora, llévate solo la idea.
Cuando partes a la mitad,
las capas crecen perezosas,
y cada capa se fusiona ligera,
así que el todo se acelera.
Este solo movimiento, partir y fusionar,
cambia la velocidad de forma drástica.

Recapitulemos

Hilado en una sola línea, va así.
Ordenar comparando uno por uno
es lento cuando la fila crece.
Así que partimos la fila por la mitad,
y partimos hasta los sueltos,
que son piezas ya ordenadas.
Fusiona esos ordenados como un cierre,
y con solo tantas fusiones como capas,
toda la fila se ordena mucho más rápido.
Partir y fusionar.
Ese es el corazón de ordenar con inteligencia.

Toca los cuatro pasos en orden para seguir una vuelta. (Partir → sueltos → fusionar → solo capas = rápido)

Aquí, fusionar siempre partió con calma a la mitad.
Pero hay un primo
que elige su punto de división algo distinto.
En vez del medio,
toma una carta como marca
y parte en menores y mayores.
Cómo elegir esa marca
lo dejo para una historia más adelante.
Por hoy, llévate solo esto:
parte a la mitad y fusiona, y se vuelve rápido.