← Volver a los ejercicios

Ordenar partiendo y mezclando

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

vueltalento señalará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

nivelcadena acadena bresultadocomparacionesacumulado

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?