Merge sort

Qué cubre este capítulo

Merge sort es el primer ordenamiento de este libro que rompe la barrera cuadrática, y lo hace con la recursión divide y vencerás de dos capítulos atrás: parte el array a la mitad, ordena cada mitad recursivamente y vuelve a unir las dos mitades ya ordenadas. Todo el truco está en que mezclar dos tramos ya ordenados cuesta apenas tiempo lineal, y hacer eso en cada nivel de la partición da O(n log n) — sin ningún caso malo, nunca. Este capítulo lo construye, observa cómo las mezclas van armando tramos ordenados cada vez más largos, y lo pone a competir contra el sort de librería del que es antepasado.

Un poco de historia

Merge sort tiene un origen inusualmente preciso: John von Neumann lo diseñó en 1945, lo que lo convierte en uno de los primerísimos algoritmos escritos para una computadora de programa almacenado. Necesitaba algo que demostrara que las nuevas máquinas podían hacer más que aritmética, y ordenar mezclando — una idea que ya se usaba a mano con tarjetas perforadas — le caía perfecto a una máquina capaz de mover datos entre posiciones de memoria. Casi ochenta años después sigue siendo la columna vertebral del ordenamiento práctico: el Timsort de Python, el Arrays.sort de Java para objetos, y prácticamente cualquier rutina de "ordena un archivo que no cabe en memoria" son merge sorts, porque mezclar es la única operación de ordenamiento que funciona de maravilla sobre datos secuenciales que solo puedes leer de principio a fin.

La intuición

Supón que ya tienes dos montones ordenados y quieres uno solo, ordenado. No los volverías a ordenar — nada más irías tomando repetidamente la menor de las dos cartas de arriba. Eso es una mezcla, y es lineal: cada carta se mira una sola vez. Merge sort no es más que esa observación aplicada recursivamente. Un solo elemento ya es un montón ordenado de uno. Dos montones ordenados de uno se mezclan en un montón ordenado de dos; dos de esos se mezclan en uno de cuatro; y así hasta que todo el array es un único montón ordenado.

Leído de arriba hacia abajo, es divide y vencerás: para ordenar un array, ordena su mitad izquierda, ordena su mitad derecha y mezcla. No te preocupas por cómo se ordenan las mitades — le confías a la recursión, exactamente el mismo salto del capítulo de Hanói. Leído de abajo hacia arriba, son los montones duplicando su tamaño: tramos de 1 se mezclan en tramos de 2, luego 4, luego 8. Las dos vistas son el mismo algoritmo, y la animación muestra la de abajo hacia arriba porque los tramos creciendo son lo interesante de ver.

Complejidad: cómo escala

El costo de merge sort es la recurrencia

— dos subproblemas de la mitad del tamaño más una mezcla lineal — y se cumple igual en el mejor caso, en el promedio y en el peor, porque la partición siempre es exactamente a la mitad sin importar los datos. Ese $O(n \log n)$ garantizado es la característica estrella de merge sort: quicksort, el capítulo que sigue, suele ser más rápido pero tiene un peor caso de $O(n^2)$; merge sort no tiene ninguno. El precio es el espacio. La mezcla necesita dónde poner el tramo combinado, así que merge sort usa $O(n)$ de memoria extra — un array auxiliar — donde los ordenamientos in-place usan O(1). La gráfica muestra el crecimiento casi lineal de $O(n \log n)$ frente a Timsort:

Las dos líneas son casi rectas — n log n crece apenas un pelo más rápido que lineal en este rango, que es justamente por lo que un sort O(n log n) se siente prácticamente gratis al lado de los sorts O(n²) del capítulo anterior.

Para qué sirve, y para qué no

Merge sort es el ordenamiento al que recurres cuando necesitas garantías. Su O(n log n) es de peor caso, no promedio, así que no hay entrada adversaria que lo degrade — valiosísimo cuando no controlas los datos o cuando un atacante los elige. Es estable, o sea que mantiene los elementos iguales en su orden original, lo cual importa cuando ordenas por una llave y quieres conservar un orden previo. Y solo lee su entrada de forma secuencial, lo que lo vuelve el algoritmo para datos que no caben en memoria (mezclar bloques ordenados leídos de disco) o para listas ligadas (que no tienen acceso aleatorio que quicksort pueda aprovechar).

Su única debilidad real es la memoria extra O(n). En un array grande, ese espacio auxiliar es un costo de verdad, y por eso un sort in-place como quicksort o heapsort suele preferirse cuando no necesitas garantías de peor caso. Merge sort cambia memoria por una garantía; que sea buen trato depende de cuál de las dos te sobra.

Los datos, o las entradas

El duelo ordena arrays de enteros aleatorios de tamaño creciente, contra Timsort. La animación corre merge sort sobre doce elementos y registra el array después de cada mezcla, para que veas cómo los tramos ordenados duplican su longitud — la vista de abajo hacia arriba de la misma recursión.

Constrúyelo, una función a la vez

La parte de "divide" es la recursión: parte en el punto medio, ordena cada lado, mezcla. Un tramo de un solo elemento es el caso base — ya está ordenado:

def merge_sort(a, probe=None):
    """O(n log n) in every case: recursively sort the two halves, then merge. The
    recurrence is T(n) = 2T(n/2) + O(n) — two half-size sorts plus a linear merge."""
    a = list(a)
    aux = list(a)
    _sort(a, aux, 0, len(a), probe)
    return a


def _sort(a, aux, lo, hi, probe):
    """Sort a[lo:hi] by splitting at the midpoint and recursing on each side. The
    base case — a run of one element — is already sorted, which stops the recursion."""
    if hi - lo <= 1:
        return
    mid = (lo + hi) // 2
    _sort(a, aux, lo, mid, probe)
    _sort(a, aux, mid, hi, probe)
    _merge(a, aux, lo, mid, hi, probe)

La mezcla es el motor. Copia los dos tramos aparte y luego recórrelos con dos dedos, tomando siempre el menor de los dos elementos del frente — y tomando el de la izquierda en los empates, que es lo que hace estable al sort:

def _merge(a, aux, lo, mid, hi, probe=None):
    """Combine two adjacent sorted runs, a[lo:mid] and a[mid:hi], into one sorted
    run in a[lo:hi]. Copy them aside, then walk both with two fingers, always
    taking the smaller front element. This is the linear-time heart of the sort —
    and taking the LEFT element on ties is what makes merge sort stable."""
    aux[lo:hi] = a[lo:hi]
    i, j = lo, mid
    for k in range(lo, hi):
        if i >= mid:                 # left run exhausted — take from the right
            a[k] = aux[j]; j += 1
        elif j >= hi:                # right run exhausted — take from the left
            a[k] = aux[i]; i += 1
        elif aux[i] <= aux[j]:       # tie goes left → stable
            a[k] = aux[i]; i += 1
        else:
            a[k] = aux[j]; j += 1
    if probe is not None:
        probe.append({"arr": list(a), "lo": lo, "hi": hi})

Míralo trabajar

Aquí está merge sort sobre doce barras, visto de abajo hacia arriba. Empieza como doce tramos ordenados de longitud uno. Cada cuadro es una mezcla: dos tramos ordenados adyacentes se combinan en un solo tramo ordenado más largo, resaltado en verde. Avanza paso a paso y observa cómo crecen los tramos verdes — longitud 2, luego 4, luego 8, luego todo el array — que son los log n niveles de la recursión ocurriendo frente a ti. Cada elemento se toca una vez por nivel, y solo hay log n niveles: ahí tienes todo el O(n log n) en una imagen:

El código completo

Las dos versiones en un solo lugar — cambia entre ellas. La pestaña from scratch es nuestro merge sort con su array auxiliar reutilizable. La pestaña de librería es sorted — Timsort, que es un merge sort que primero encuentra los tramos que ya vienen ordenados de forma natural en tus datos y luego los mezcla, usando insertion sort para armar los tramos chicos.

"""Merge sort — the first O(n log n) sort, and the cleanest example of
divide-and-conquer. Split the array in half, sort each half by recursing, then
merge the two sorted halves into one. The merge is the clever part: combining two
already-sorted runs takes only linear time, and doing that at every level of the
split is what buys O(n log n) with no bad case.

It's implemented here in the index-based, in-place style real libraries use — one
auxiliary array reused across all the merges — so the animation can watch each
merge produce a longer sorted run.
"""


# region: divide
def merge_sort(a, probe=None):
    """O(n log n) in every case: recursively sort the two halves, then merge. The
    recurrence is T(n) = 2T(n/2) + O(n) — two half-size sorts plus a linear merge."""
    a = list(a)
    aux = list(a)
    _sort(a, aux, 0, len(a), probe)
    return a


def _sort(a, aux, lo, hi, probe):
    """Sort a[lo:hi] by splitting at the midpoint and recursing on each side. The
    base case — a run of one element — is already sorted, which stops the recursion."""
    if hi - lo <= 1:
        return
    mid = (lo + hi) // 2
    _sort(a, aux, lo, mid, probe)
    _sort(a, aux, mid, hi, probe)
    _merge(a, aux, lo, mid, hi, probe)
# endregion


# region: merge
def _merge(a, aux, lo, mid, hi, probe=None):
    """Combine two adjacent sorted runs, a[lo:mid] and a[mid:hi], into one sorted
    run in a[lo:hi]. Copy them aside, then walk both with two fingers, always
    taking the smaller front element. This is the linear-time heart of the sort —
    and taking the LEFT element on ties is what makes merge sort stable."""
    aux[lo:hi] = a[lo:hi]
    i, j = lo, mid
    for k in range(lo, hi):
        if i >= mid:                 # left run exhausted — take from the right
            a[k] = aux[j]; j += 1
        elif j >= hi:                # right run exhausted — take from the left
            a[k] = aux[i]; i += 1
        elif aux[i] <= aux[j]:       # tie goes left → stable
            a[k] = aux[i]; i += 1
        else:
            a[k] = aux[j]; j += 1
    if probe is not None:
        probe.append({"arr": list(a), "lo": lo, "hi": hi})
# endregion

"""Python's `sorted` is Timsort, which is itself a merge sort at heart — it finds
already-sorted runs in the data and merges them (using insertion sort to build up
small runs first). So this face-off is our textbook merge sort against a production
merge sort: same O(n log n), same stability, but Timsort is adaptive (near-linear on
nearly-sorted input) and written in C.
"""


# region: sort_builtin
def sort_builtin(a):
    """Timsort: an adaptive, stable merge sort. O(n log n) worst case, O(n) on
    already-sorted input, implemented in C."""
    return sorted(a)
# endregion

Desde cero vs librería

Misma clase de algoritmo, misma estabilidad, así que la diferencia es la constante de siempre. Ordenar 80000 enteros le tomó a nuestro merge sort unos 86 ms contra los 7.5 ms de Timsort — como once veces más lento. Timsort gana por tres razones, todas factores constantes: está en C y no en Python, es adaptativo (aprovecha los tramos que ya vienen ordenados en los datos, que nuestra versión de libro de texto atraviesa a ciegas) y evita reservar memoria en cada mezcla. Nada de eso cambia el O(n log n) — ambas líneas tienen la misma forma — y ese es el resultado tranquilizador. Construiste el algoritmo sobre el que está construida la librería; la librería nada más lo corre más rápido. Y la estabilidad te salió gratis, la misma propiedad que garantiza sorted, de la sola decisión de tomar el elemento de la izquierda en los empates.

Dónde te lo vas a encontrar de verdad

Merge sort es el ordenamiento detrás del ordenamiento estable en todos lados. El sorted y el list.sort de Python, el sort de objetos de Java y el sort estable de Rust son todos Timsort o parientes cercanos — merge sorts afinados para datos reales. Su naturaleza de acceso secuencial lo vuelve el algoritmo del ordenamiento externo: las bases de datos y los sistemas de big data ordenan terabytes mezclando bloques ordenados que van llegando desde disco, exactamente la idea de von Neumann a escala. Es el sort natural para listas ligadas, que quicksort no puede tocar de forma eficiente. Y la operación de mezcla en sí, independiente del sort, es una bestia de carga — mezclar streams ordenados está debajo de las bases de datos log-structured, los diffs de los sistemas de control de versiones y el paso de mezcla de los joins externos.

Conclusiones

Merge sort parte el array a la mitad, ordena recursivamente cada mitad y mezcla los dos tramos ordenados — $O(n \log n)$ en todos los casos porque la partición no depende de los datos, y estable porque los empates se van a la izquierda. El costo son $O(n)$ de memoria extra para la mezcla. Su garantía (ningún caso malo) y su estabilidad lo convierten en el sort de elección cuando no puedes predecir la entrada o necesitas conservar el orden, y su acceso secuencial lo vuelve el sort para datos más grandes que la memoria.

El siguiente capítulo es su gran rival, quicksort — también O(n log n) en promedio, también divide y vencerás, pero in-place y normalmente más rápido en la práctica, al precio de un peor caso O(n²) que merge sort no tiene. Comparar los dos es la lección más clara del libro sobre cómo una misma clase asintótica puede esconder trade-offs muy distintos en el mundo real.