← Volver a los ejercicios

msort: dividir, ordenar cada mitad y mezclar

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.

1. El código y el árbol de llamadas

paso 0 de 0
devuelve:
–
■ línea 13: la llamada parte su lista en dos mitades ■ línea 14: cada mitad se ordena con msort y las dos entran a merge ■ líneas 3 a 8: merge toma un elemento por paso

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.

2. La mezcla, fila por fila

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.

3. Lo que se lleva de aquí

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.