Merge sort hace tres cosas en cada llamada: parte la lista
en dos con splitAt, ordena cada mitad con la misma función y
mezcla las dos mitades ya ordenadas. La partición baja por el árbol de
llamadas y la mezcla sube. Avance paso a paso y mire en qué momento una
llamada deja de dividir y empieza a mezclar.
Cada caja es una llamada a msort. En azul, la
que está dividiendo; en ámbar, la que está mezclando, con la salida que ya
tiene armada; en verde, la que ya devolvió su lista ordenada. Las cajas de
la última fila son las listas de un elemento, donde n == 0 y la
recursión se detiene.
Una fila por cada elemento que
merge pone en la salida. La comparación m < n
mira solo las dos cabezas, nunca el resto de las listas.
Las tres partes están en dos líneas de código.
val (izq, der) = xs.splitAt(n) divide y no compara nada:
List(5, 2, 4, 1) se parte en List(5, 2) y
List(4, 1) por la posición, no por el valor. En
merge(msort(izq), msort(der)) las dos llamadas internas tienen
que devolver antes de que merge empiece, así que cuando la
mezcla corre sus dos argumentos ya están ordenados. Eso es lo que permite
comparar solo las cabezas.
El contador de la línea 13 cuenta las divisiones y el de las líneas 7 y 8
cuenta las comparaciones. Con cuatro elementos hay tres divisiones y las
comparaciones caben en los dedos; con el doble de elementos el árbol gana
un nivel y no el doble, que es de donde sale el costo
n log n.
El caso base no ordena nada: if (n == 0) xs devuelve la
lista tal como llegó, y con uno o cero elementos eso ya está ordenado. Toda
la ordenación ocurre en merge, en el camino de vuelta. Si
merge recibiera dos listas desordenadas, la comparación de las
cabezas no bastaría y el resultado saldría mal sin que ninguna línea
fallara.