Merge sort en Python — explicado paso a paso (con animación)

Merge sort es el algoritmo de ordenación que da una garantía absoluta: ordena en O(n log n) siempre, da igual la entrada. Sin sorpresas, sin peor casos catastróficos como quicksort, sin sensibilidad a si la lista ya estaba casi ordenada. Ese determinismo lo convierte en la opción correcta cuando importa la previsibilidad: backends serios, ordenaciones estables, escenarios donde “casi siempre rápido” no basta.

La analogía es perfectamente cotidiana: juntar dos mazos de cartas ya ordenados en uno solo. Miras la carta de arriba de cada mazo, coges la menor, repites hasta vaciar los dos. Esa operación, aplicada recursivamente, es merge sort.

Esta entrada cubre el algoritmo en serio: cómo funciona paso a paso, implementación en Python, JavaScript y Java, su complejidad real, por qué nunca se degrada, su único punto débil (la memoria) y por qué Timsort (el que Python usa de verdad) lo lleva dentro como mitad del híbrido.

Si quieres el panorama de los 14 algoritmos del clúster: Algoritmos de ordenación en Python — los 14 explicados.

Merge sort en una frase

Divide la lista por la mitad recursivamente hasta tener trozos de un elemento. Después fusiona pares de trozos ordenados, de abajo arriba, hasta volver a tener una sola lista. El secreto está en cómo fusionas: dos listas YA ordenadas se combinan en una sola ordenada en O(n).

Animación sobre 12 valores con sus contadores en vivo. Fíjate en cómo las barras cambian de altura “en su sitio” — eso es merge sobrescribiendo posiciones, no intercambiando:

Antes de seguir: qué quieren decir O, Θ y Ω

En la tabla de complejidad verás los tres símbolos. Idea rápida:

• O(n log n) — “O grande”, cota superior (peor caso).
• Ω(n log n) — “Omega”, cota inferior (mejor caso). En merge sort, es igual de buena que la superior.
• Θ(n log n) — “Theta”: el caso típico. Es n log n, sin sorpresas.

Merge sort es Θ(n log n) literalmente: mejor caso y peor caso coinciden. Eso es lo que lo hace tan predecible. Más detalle en el pilar del clúster.

Cómo funciona — traza paso a paso

Ordenamos [3, 1, 4, 1, 5] a mano.

Fase 1: divide hasta tener trozos de uno.

              [3, 1, 4, 1, 5]
              /             
        [3, 1, 4]          [1, 5]
        /                 /    
     [3]    [1, 4]       [1]   [5]
             /   
           [1]  [4]

Las “hojas” del árbol ([3], [1], [4], [1], [5]) están ya “ordenadas” trivialmente.

Fase 2: fusiona pares de listas ordenadas, de abajo arriba.

Fusionar [1] con [4]:
– Cabezas: 1, 4. Menor: 1. Cojo 1.
– Cabezas: nada, 4. Cojo 4.
– Resultado: [1, 4].

Fusionar [3] con [1, 4]:
– Cabezas: 3, 1. Menor: 1. Cojo 1.
– Cabezas: 3, 4. Menor: 3. Cojo 3.
– Cabezas: nada, 4. Cojo 4.
– Resultado: [1, 3, 4].

Fusionar [1] con [5]:
– Cabezas: 1, 5. Menor: 1. Cojo 1.
– Cabezas: nada, 5. Cojo 5.
– Resultado: [1, 5].

Fusionar [1, 3, 4] con [1, 5]:
– Cabezas: 1, 1. Iguales — por ser estable, cojo el de la izquierda → 1.
– Cabezas: 3, 1. Menor: 1. Cojo 1.
– Cabezas: 3, 5. Menor: 3. Cojo 3.
– Cabezas: 4, 5. Menor: 4. Cojo 4.
– Cabezas: nada, 5. Cojo 5.
– Resultado: [1, 1, 3, 4, 5].

Ordenado. El árbol tiene profundidad ~log₂(5) ≈ 3, y cada nivel hace O(n) trabajo de fusión. Total: O(n log n). Siempre.

Implementación en Python (clásica)

def ordenar(lista: list[int]) -> list[int]:
    if len(lista) <= 1:
        return lista
    medio = len(lista) // 2
    izquierda = ordenar(lista[:medio])
    derecha = ordenar(lista[medio:])
    return fusionar(izquierda, derecha)


def fusionar(izq: list[int], der: list[int]) -> list[int]:
    resultado = []
    i = j = 0
    while i < len(izq) and j < len(der):
        if izq[i] <= der[j]:
            resultado.append(izq[i])
            i += 1
        else:
            resultado.append(der[j])
            j += 1
    resultado.extend(izq[i:])
    resultado.extend(der[j:])
    return resultado


if __name__ == "__main__":
    print(ordenar([3, 1, 4, 1, 5]))  # [1, 1, 3, 4, 5]

Cuatro detalles importantes:

1. <= (menor o igual) en la comparación de la fusión: esto es lo que hace que merge sort sea estable (cuando hay empate, mantiene el orden original).
2. Slicing lista[:medio] y lista[medio:] crea listas nuevas → memoria O(n). Esa es la pega del merge sort clásico.
3. extend() al final añade el resto de la lista que quedó sin consumir (típicamente toda la cola de una de las dos).
4. Recursión natural divide-y-vencerás.

En entrevistas, si el entrevistador te pide “merge sort in-place”, lleva preparado el matiz: existen variantes “in-place” (con O(1) memoria extra), pero son significativamente más lentas (O(n log² n)) y complicadas. Casi nadie las usa. La versión clásica con O(n) memoria es la que se enseña y la que se usa.

Implementación en JavaScript

function ordenar(lista) {
  if (lista.length <= 1) return lista;
  const medio = Math.floor(lista.length / 2);
  const izquierda = ordenar(lista.slice(0, medio));
  const derecha = ordenar(lista.slice(medio));
  return fusionar(izquierda, derecha);
}

function fusionar(izq, der) {
  const resultado = [];
  let i = 0, j = 0;
  while (i < izq.length && j < der.length) {
    if (izq[i] <= der[j]) {
      resultado.push(izq[i++]);
    } else {
      resultado.push(der[j++]);
    }
  }
  return [...resultado, ...izq.slice(i), ...der.slice(j)];
}

console.log(ordenar([3, 1, 4, 1, 5])); // [1, 1, 3, 4, 5]

Implementación en Java

public static int[] ordenar(int[] lista) {
    if (lista.length <= 1) return lista;
    int medio = lista.length / 2;
    int[] izquierda = ordenar(Arrays.copyOfRange(lista, 0, medio));
    int[] derecha = ordenar(Arrays.copyOfRange(lista, medio, lista.length));
    return fusionar(izquierda, derecha);
}

private static int[] fusionar(int[] izq, int[] der) {
    int[] resultado = new int[izq.length + der.length];
    int i = 0, j = 0, k = 0;
    while (i < izq.length && j < der.length) {
        if (izq[i] <= der[j]) {
            resultado[k++] = izq[i++];
        } else {
            resultado[k++] = der[j++];
        }
    }
    while (i < izq.length) resultado[k++] = izq[i++];
    while (j < der.length) resultado[k++] = der[j++];
    return resultado;
}

Complejidad — la garantía absoluta

Métrica	Mejor caso	Caso medio	Peor caso
Tiempo	Ω(n log n)	Θ(n log n)	O(n log n)
Memoria	O(n)	O(n)	O(n)
Estable	Sí	Sí	Sí

Lo más bonito de merge sort: las tres columnas son iguales. Mejor caso = peor caso = O(n log n). No hay sorpresas.

Demostración rápida:
– El árbol de recursión tiene profundidad exactamente log₂(n).
– En cada nivel, todas las fusiones juntas tocan los n elementos una vez → O(n) por nivel.
– Total: n × log n = O(n log n).

Por qué la memoria es O(n). En cada nivel de recursión necesitas un buffer auxiliar del tamaño del tramo para fusionar. La versión clásica crea listas nuevas; las versiones “smart” reutilizan un único buffer de tamaño n. En cualquier caso, O(n).

Por qué es estable. La comparación <= (no <) en la fusión garantiza que, ante un empate, se elige primero el de la lista izquierda (que viene “antes” en el orden original). Los iguales mantienen su orden relativo.

Ver en acción — merge sort sobre 10 listas fijas (la consistencia hecha tabla)

Todo el clúster usa las mismas 10 listas fijas (n=15) para que sea justa la comparativa cruzada:

#	Nombre	Qué es
1	ordenada	1, 2, 3, ..., 15
2	inversa	15, 14, ..., 1
3	casi_ordenada	1..15 con un par de swaps
4	muy_desordenada	Patrón min-max alternado [1, 15, 2, 14, ...]
5	duplicados	Enteros del rango [1..5] repetidos
6-10	aleatoria_s1 .. aleatoria_s5	5 permutaciones aleatorias deterministas

Aplicamos merge sort sobre las 10:

from sortlab import bench_estandar, formato_tabla
print(formato_tabla(bench_estandar("merge", n=15)))

Salida real:

Lista            Comp.  Interc.  Escr.  Tiempo (ms)   Caso  Θ observada
---------------  -----  -------  -----  -----------  -----  -----------
ordenada         31           0     59        0.010  Único   Θ(n log n)
inversa          28           0     59        0.010  Único   Θ(n log n)
casi_ordenada    39           0     59        0.011  Único   Θ(n log n)
muy_desordenada  40           0     59        0.010  Único   Θ(n log n)
duplicados       43           0     59        0.010  Único   Θ(n log n)
aleatoria_s1     40           0     59        0.010  Único   Θ(n log n)
aleatoria_s2     43           0     59        0.011  Único   Θ(n log n)
aleatoria_s3     43           0     59        0.011  Único   Θ(n log n)
aleatoria_s4     40           0     59        0.011  Único   Θ(n log n)
aleatoria_s5     42           0     59        0.011  Único   Θ(n log n)

Mira la columna Escr. — 59 en TODAS las filas. Da igual cómo esté la entrada: merge sort hace siempre el mismo número de escrituras, exactamente las que dicta su estructura recursiva (independiente del contenido). Es la firma de merge en cifras.

La columna Comp. varía un poco (entre 28 y 43) porque la fusión “para antes” cuando una mitad se agota. Pero el rango es estrechísimo: menos del doble entre el mejor y el peor. Ninguna lista lo descoloca. Por eso la librería lo clasifica como Único + Θ(n log n) consistentemente.

Compara con quicksort sobre las mismas listas (datos reales):

Lista	Merge (comp.)	Quick (comp.)
ordenada	31	105
inversa	28	105
casi_ordenada	39	96
aleatoria_s1	40	51

Quicksort PUEDE ser más rápido en aleatoria (51 vs 40), pero el problema es que también puede ser 3 veces más lento (105 vs 31) cuando le toca una lista ya ordenada. Merge nunca te traiciona. Esa es la pregunta clave del sistema: ¿quieres “más rápido a veces” o “consistente siempre”?

¿Y el escalado a n grande? Sobre aleatoria_s1:

n	Comparaciones	Tiempo
100	555	0,1 ms
1.000	8.702	1,6 ms
10.000	120.560	21 ms

Multiplicas n por 10 → comparaciones se multiplican por ~14 (no por 10, por ese log n extra). Eso es Θ(n log n) en cifras reales. Frente a bubble (5,4 segundos para n=10.000), merge tarda 21 ms: 256 veces más rápido, y sin ningún caso degradado en el camino.

Reproducirlo sin instalar nada

sortlab vive privado en el Python profesional: medir, optimizar y escalar (con la implementación completa explicada y la conexión con Timsort). Para reproducir sin la librería, esta es la versión instrumentada inline:

def merge_medido(lista_original: list[int]) -> dict:
    arr = list(lista_original)
    metricas = {"comparaciones": 0, "escrituras": 0}
    aux = arr.copy()

    def ms(lo: int, hi: int) -> None:
        if lo >= hi:
            return
        mid = (lo + hi) // 2
        ms(lo, mid)
        ms(mid + 1, hi)
        for k in range(lo, hi + 1):
            aux[k] = arr[k]
        i, j = lo, mid + 1
        for k in range(lo, hi + 1):
            if i > mid:
                arr[k] = aux[j]; j += 1
            elif j > hi:
                arr[k] = aux[i]; i += 1
            else:
                metricas["comparaciones"] += 1
                if aux[i] <= aux[j]:
                    arr[k] = aux[i]; i += 1
                else:
                    arr[k] = aux[j]; j += 1
            metricas["escrituras"] += 1

    if arr:
        ms(0, len(arr) - 1)
    return {"ordenada": arr, **metricas}


listas = {
    "ordenada":         list(range(1, 16)),
    "inversa":          list(range(15, 0, -1)),
    "casi_ordenada":    [1, 11, 3, 4, 5, 6, 7, 8, 9, 10, 2, 12, 13, 14, 15],
    "muy_desordenada":  [1, 15, 2, 14, 3, 13, 4, 12, 5, 11, 6, 10, 7, 9, 8],
    "duplicados":       [1, 1, 3, 2, 2, 2, 1, 5, 1, 5, 4, 1, 1, 1, 2],
}
for nombre, lista in listas.items():
    r = merge_medido(lista)
    print(f"{nombre:<16}  comp={r['comparaciones']:>3}  esc={r['escrituras']:>3}")

Verás: comparaciones varían entre 28 y 43; escrituras siempre 59. La firma de merge en cifras.

Mitos que circulan sobre merge sort

• “Merge sort es más lento que quicksort.” En el caso medio sí, ligeramente. En el peor caso, merge es mucho más rápido (O(n log n) frente al O(n²) de quick). La elección depende de si te importa el peor caso.
• “Merge necesita siempre O(n) memoria extra.” Cierto en la versión clásica. Existen variantes “in-place” con O(1) memoria extra, pero son O(n log² n) y mucho más complicadas; casi nadie las usa.
• “No se usa en producción porque hay quicksort.” Falso. Java lo usa para ordenar objetos (Collections.sort y List.sort), Python lo usa como mitad de Timsort, y bases de datos como PostgreSQL lo usan para ORDER BY cuando no cabe todo en memoria (es lo que se llama “external merge sort”).

¿Y en la stdlib de Python?

Indirectamente. No hay merge_sort() accesible, pero cada vez que llamas a list.sort() o sorted() estás ejecutando Timsort, que es básicamente merge sort + insertion. La fase de fusión es merge sort literal, escrita en C en Objects/listobject.c de CPython.

Trivia algorítmica

Merge sort lo inventó John von Neumann en 1945. Lo describió en un manuscrito para el ordenador EDVAC, uno de los primeros computadores electrónicos digitales de la historia. Es decir: el algoritmo lleva 80 años en uso y sigue siendo la mitad de lo que Python ejecuta cada vez que ordenas una lista. Hay pocos algoritmos con esa longevidad.

Cuándo usar merge sort (más a menudo de lo que crees)

Sí:

• Cuando importa la previsibilidad. Garantiza O(n log n) — útil en sistemas con SLAs donde “peor caso O(n²)” es inaceptable.
• Cuando necesitas estabilidad. Si ordenas objetos por una clave y quieres preservar el orden original ante empates, merge sort lo da gratis.
• Para ordenar listas enlazadas. Merge sort se adapta perfectamente: no necesita acceso aleatorio. Es el algoritmo de elección para listas enlazadas.
• External sort (ordenar datos que no caben en memoria): la idea de merge sort se extiende a archivos en disco. Es la base de algoritmos como “external merge sort” usados en bases de datos.

No:

• Cuando la memoria es escasa. Si no puedes pagar O(n) extra, mira heapsort (O(1) memoria y también O(n log n) garantizado).
• Si tienes sorted() o Arrays.sort() disponibles. Casi siempre serán más rápidos en la práctica gracias a sus optimizaciones internas.

Comparativa rápida

Dónde encaja merge dentro del clúster:

Algoritmo	Mejor	Peor	Memoria	Estable	Ventaja
Quicksort	Ω(n log n)	O(n²)	O(log n)	No	Súper rápido en la práctica
Merge sort	Ω(n log n)	O(n log n)	O(n)	Sí	Sin sorpresas; estable
Heapsort	Ω(n log n)	O(n log n)	O(1)	No	Mismo Big-O, sin memoria extra
Insertion	Ω(n)	O(n²)	O(1)	Sí	Rey de listas pequeñas
Timsort	Ω(n)	O(n log n)	O(n)	Sí	El que Python usa: merge + insertion

La pieza interesante: merge sort es la mitad de Timsort. Cuando Python ordena, llama a Timsort, que internamente identifica tramos cortos y los fusiona usando merge sort. Es decir: cada vez que haces lista.sort(), una parte de merge sort se está ejecutando bajo el capó.

FAQ rápida

¿Merge sort es siempre O(n log n)?
Sí, en cualquier entrada. No hay peor caso degradado como en quicksort.

¿Merge sort puede ser in-place?
Existen variantes con O(1) memoria extra, pero son O(n log² n) y mucho más complicadas. En la práctica nadie las usa; la versión clásica O(n) memoria es estándar.

¿Por qué es estable?
Porque la comparación de la fusión usa <= en lugar de <. Ante un empate, el de la izquierda se elige primero, manteniendo el orden original.

¿Funciona bien para listas enlazadas?
Excepcionalmente. No necesita acceso aleatorio, así que es el algoritmo de elección cuando trabajas con listas enlazadas (donde quicksort sufre).

¿Por qué Timsort es básicamente “merge sort mejorado”?
Porque Timsort = insertion (para tramos cortos) + merge (para fusionar tramos ordenados). Aprovecha que muchas listas reales ya están parcialmente ordenadas, identifica “runs” naturales y los fusiona con merge.

En resumen

Merge sort es la opción correcta cuando importa la garantía. Su O(n log n) absoluto, su estabilidad y su adaptabilidad (listas enlazadas, ordenación externa en disco) lo hacen indispensable en sistemas serios. La pega es la memoria O(n), que en escenarios constreñidos pesa. Y lo más importante: forma la mitad de Timsort, el algoritmo que Python ejecuta cada vez que llamas a sorted().

Si quieres aprender a medir cuándo merece la pena pagar memoria a cambio de garantías y a elegir bien los algoritmos para producción, ese es el camino del curso de El Pythonista.