← Volver a los ejercicios

merge: prediga cuál cabeza sale en cada paso

Dentro de msort, merge recibe dos listas que ya vienen ordenadas y las junta en una sola. Nunca mira más que las dos cabezas: compara m con n y una de las dos se va a la salida. Diga en cada paso cuál sale y compruébelo.

1. La función y las dos listas

Las dos listas de cada pareja llegan ordenadas, que es la condición con que msort llama a merge: las dos mitades ya pasaron por msort. El contador de cada línea sube con los pasos acertados, y la línea resaltada es la del último paso.

2. ¿Qué sale en este paso?

3. Lo que se lleva de aquí

La comparación es entre dos elementos y nada más. En merge(List(2, 5), List(1, 4)) el primer paso compara 2 con 1 y el 5 ni se mira: como las dos listas vienen ordenadas, nada que esté detrás de una cabeza puede ser menor que ella. Por eso merge recorre cada lista una sola vez y el total de pasos es la suma de los dos tamaños.

El paso que sale lo decide el if, y el que se queda vuelve a competir. Cuando sale m, la llamada sigue con merge(ms, l2): la cola de l1 y l2 completa, porque n todavía no ha salido. Esa asimetría entre los dos argumentos es lo que hace que la salida quede ordenada sin comparar nada más.

Los dos primeros casos son los que terminan la recursión, y devuelven la lista que sobró entera. Con (List(5), Nil) el resultado es List(5) de una vez, sin comparar. Ahí se ve que una de las dos listas se agota antes que la otra, y que el resto no necesita trabajo: ya estaba ordenado cuando entró.