La lista enlazada es 7 → 3 → 8 → 1 → 5 → 2 y se
ordena con merge sort: partir la corta en dos,
ordenar se llama sobre cada mitad y mezclar empalma
los nodos sin copiar datos.
1. Dónde corta partir
primera mitad:segunda mitad:
2. El lento y el rápido, vuelta por vuelta
vuelta
lento señala
rápido señala
El rápido avanza dos nodos por cada uno del lento. Cuando
el rápido se queda sin pareja, el lento está en el último nodo de la primera
mitad, y ahí se corta.
3. El total de comparaciones
Cada mezclar compara un dato de cada
cadena y se lleva el menor. Sumando todas las mezclas de la recursión, hasta
dejar la lista ordenada, ¿cuántas comparaciones hace?
4. Las mezclas en el orden en que ocurren
nivel
cadena a
cadena b
resultado
comparaciones
acumulado
5. La mezcla de arriba
La última mezcla junta dos cadenas de tres nodos y
hace cuatro comparaciones, no seis. ¿Por qué se ahorra las dos últimas?
Lo que quedó
Partir cuesta un recorrido y no copia nada; mezclar cuesta
una comparación por nodo que sale, y menos cuando una cadena se agota antes.
Cada nivel de la recursión toca los n nodos una vez y hay
⌈log₂ n⌉ niveles: Θ(n log n) en tiempo, con Θ(1) de espacio en la mezcla
porque lo único que se reescribe es el campo siguiente.