merge: prediga cuál cabeza sale en cada pasoDentro 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.
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.
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ó.