El ordenamiento por inserción (04-02) toca techo en Θ(n²) porque mueve los elementos de uno en uno. Para romper esa barrera aplicaremos, por fin en su forma pura, la estrategia de 03-01: merge sort es el hijo directo de divide y vencerás — divide la lista en dos mitades, las ordena recursivamente y las mezcla. Todo su ingenio vive en esa mezcla: combinar dos listas ya ordenadas en una sola cuesta solo O(n). En esta lección construiremos primero la función merge, luego el algoritmo completo, lo trazaremos sobre ocho llegadas de RutaBus con el árbol de división y mezcla, y saldaremos la deuda más antigua del curso: resolver con rigor la recurrencia T(n) = 2·T(n/2) + O(n) que dejamos anotada en 03-01. Cerraremos con sus costes (estable, pero no in-place) y sus usos reales, del ordenamiento de ficheros gigantes al Timsort de Python.

1. La idea: el trabajo se hace al combinar
2. La función merge: dos punteros sobre dos listas ordenadas
3. Implementación completa de merge sort
4. Traza: el árbol de división y mezcla con 8 llegadas
5. La recurrencia T(n) = 2·T(n/2) + O(n), resuelta por niveles
6. Estabilidad y coste espacial: el precio del O(n log n)
7. Merge sort en el mundo real: ordenación externa y Timsort

Recordemos el esquema de 03-01 — dividir, conquistar, combinar — y apliquémoslo al ordenamiento:

1. Dividir: parte la lista en dos mitades (trivial: un corte por el centro).
2. Conquistar: ordena cada mitad recursivamente con el propio merge sort. Caso base: una lista de 0 o 1 elementos ya está ordenada.
3. Combinar: mezcla las dos mitades ordenadas en una sola lista ordenada.

Fíjate en dónde vive la inteligencia: dividir es un corte tonto y conquistar es delegar en la recursión. Toda la chicha está en el paso 3. Esta distribución del esfuerzo — dividir barato, combinar trabajoso — es la seña de identidad de merge sort; en la próxima lección veremos su espejo exacto (quick sort: dividir trabajoso, combinar gratis).

¿Por qué esto puede batir a la inserción? Porque mezclar dos listas ordenadas de tamaño n/2 no requiere comparar todos con todos: como ambas ya están ordenadas, basta un recorrido simultáneo. Ese "basta un recorrido" es la mina de oro.

El problema auxiliar: dadas dos listas ya ordenadas, producir una lista ordenada con todos sus elementos. La técnica se llama de los dos punteros: un índice por lista, y en cada paso se copia el menor de los dos candidatos.

Piensa en dos montones de fichajes de la L1 y la L2, cada uno ya ordenado por hora, que hay que fusionar en un listado único: miras la ficha superior de cada montón, pasas la más temprana al listado, y repites.

Punto por punto:

• Los dos punteros solo avanzan: i recorre izq y j recorre der, cada uno de izquierda a derecha, sin retroceder jamás. Cada comparación copia exactamente un elemento al resultado, así que el bucle da a lo sumo len(izq) + len(der) vueltas: merge es O(n) en el total de elementos. Invariante: resultado contiene, ordenados, todos los elementos ya consumidos, y todo lo pendiente es ≥ que el último copiado.
• <= en vez de <: ante un empate copiamos primero el de la lista izquierda — el que estaba antes en la lista original. Así los empates conservan su orden relativo: es el detalle que hará estable al merge sort completo, igual que el > estricto lo era en la inserción (04-02).
• Los restos (extend): cuando una lista se agota, la otra puede tener cola pendiente; como está ordenada y todos sus elementos son mayores que lo ya copiado, se añade en bloque.

Ejemplo directo con dos paneles ordenados:

Con merge resuelto, el algoritmo completo es corto — divide y vencerás en estado puro, compárese con la plantilla de 03-01:

• El caso base corta la recursión en listas de tamaño ≤ 1, que ya están ordenadas por definición. Sin él, lista[:0] y las llamadas seguirían para siempre — el error clásico de 03-01.
• Los cortes lista[:medio] y lista[medio:] copian las sublistas (coste oculto de Python, 02-01). Es cómodo pero contribuye al coste espacial que analizaremos en el apartado 6.
• A diferencia de ordenar_insercion, esta versión devuelve una lista nueva en vez de modificar la original: estilo funcional, más fácil de razonar.

Ordenemos las 8 llegadas acumuladas del panel de Estación Norte:

El proceso dibuja dos pirámides: una de división (hacia abajo) y una de mezcla (hacia arriba):

Lectura del árbol:

• Bajada (división): 8 → 4+4 → 2+2+2+2 → ocho hojas de 1 elemento. Con n = 8 = 2³ hay exactamente 3 niveles de división: log₂ 8, el conteo de niveles de 03-01.
• Subida (mezcla): las hojas se mezclan por pares. Sigamos una: merge(["18:42"], ["18:07"]) → ["18:07", "18:42"]. Luego merge(["18:07","18:42"], ["18:31","18:59"]) → ["18:07","18:31","18:42","18:59"]: los punteros van saltando entre listas (18:07 de izq, 18:31 de der, 18:42 de izq...). La mezcla final entrelaza dos mitades de 4.
• Cada nivel de mezcla toca los 8 elementos exactamente una vez: 4 merges de 2, luego 2 merges de 4, luego 1 merge de 8 — siempre 8 copias por nivel. Guarda este dato: es la clave del análisis.

En 03-01 escribimos la recurrencia y prometimos resolverla aquí. Merge sort la encarna literalmente:

Método de los niveles (el de 03-01, ahora con todas las cuentas). Desplegamos el árbol de llamadas y sumamos el trabajo no recursivo (la mezcla) nivel a nivel:

El patrón que vimos en la traza es general: cada nivel cuesta exactamente c·n, porque al bajar un nivel los subproblemas se duplican pero su tamaño se reduce a la mitad — el producto no cambia. Y el número de niveles es el de veces que se puede partir n por la mitad: log₂ n (04-01 lo llamaba "contar mitades").

Deuda saldada. Y con un extra: en merge sort este coste no depende de la entrada. La mezcla recorre siempre las dos listas completas, esté el panel ya ordenado, invertido o aleatorio:

Esa esquina inferior izquierda es la garantía incondicional que el análisis de peor caso (02-03) nos enseñó a valorar: merge sort es predecible como un reloj. El precio: no aprovecha los datos casi ordenados como la inserción (su mejor caso también es n log n).

Para calibrar la victoria: con n = 10.000 expediciones, inserción promedia ≈ n²/4 = 25.000.000 de operaciones; merge sort, ≈ n·log₂ n ≈ 132.000. Casi 200 veces menos.

Estabilidad: sí. El <= de merge garantiza que ante un empate se copia primero el elemento de la mitad izquierda — el que precedía en la lista original. Como esto se cumple en cada mezcla de cada nivel, el orden relativo de los empates sobrevive hasta el final. Merge sort ordena por hora un panel de tuplas (hora, línea) sin desordenar los empates (el ejemplo de 04-02).

Espacio: O(n) auxiliar — no es in-place. Cada merge construye una lista resultado nueva, y los cortes lista[:medio] copian. Con el análisis de 02-02: en el momento de la mezcla final conviven la entrada y el resultado — Θ(n) de memoria extra —, más los O(log n) marcos de la pila de recursión (dominados por el n anterior). Compárese con el O(1) de la inserción:

Es el trade-off tiempo ↔ espacio de 02-02 en su versión de manual: merge sort compra velocidad garantizada pagando memoria. (Existen variantes in-place de merge sort, pero son notoriamente intrincadas y raras en la práctica; la respuesta habitual a "quiero n log n sin memoria extra" es otra: quick sort, en la próxima lección.)

Ordenación externa. Supón el histórico anual de fichajes de RutaBus: 500 GB que no caben en los 32 GB de RAM del servidor. Merge sort es el único de nuestros algoritmos que trabaja cómodo así, porque merge solo necesita leer las listas secuencialmente, de principio a fin:

1. Lee el fichero en bloques que sí quepan en RAM, ordena cada bloque (con lo que sea) y escríbelo a disco: obtienes muchos tramos ordenados.
2. Mezcla los tramos leyéndolos en paralelo con la técnica de punteros — cada fichero se lee secuencialmente, que es justo lo que los discos hacen rápido — hasta dejar uno solo.

Este esquema (external merge sort) es la base de cómo ordenan las bases de datos y los frameworks de big data cuando los datos no caben en memoria.

Timsort: el círculo se cierra. El sorted() y el list.sort() de Python usan Timsort, un híbrido diseñado en 2002 para la propia Python que combina... nuestras dos últimas lecciones:

• Detecta runs: tramos ya ordenados presentes en los datos reales (los paneles casi ordenados de 04-02), y los extiende con ordenamiento por inserción — aprovechando que en tramos cortos y casi ordenados es imbatible.
• Mezcla los runs con un merge afinado, manteniendo la estabilidad y la garantía O(n log n) del peor caso.

Resultado: O(n) sobre datos ya ordenados (herencia de la inserción), O(n log n) garantizado (herencia del merge), y estable. Cuando en 02-01 dábamos por hecho que sorted costaba O(n log n), era esto lo que había debajo. Moraleja de ingeniería: los algoritmos "de libro" no compiten entre sí, se combinan — cada uno cubriendo el punto débil del otro.

• Olvidar el caso base (len(lista) <= 1): la recursión no termina nunca (RecursionError). Es el primer punto a revisar en cualquier divide y vencerás, como ya avisamos en 03-01.
• Olvidar los restos en merge: sin los extend finales, los elementos de la lista no agotada se pierden. Síntoma: el resultado sale ordenado... pero más corto que la entrada. Comprueba siempre len(resultado) == len(izq) + len(der).
• Usar < en vez de <= en merge: sigue ordenando bien, pero ante empates copia primero el de la derecha y rompe la estabilidad — el mismo error silencioso que el >= de la inserción. Solo un test con claves duplicadas lo detecta.
• medio mal calculado (len(lista) / 2 con / devuelve float y rompe el slicing; o dividir en [:medio+1] y [medio:] duplica el elemento central). El corte correcto es exhaustivo y disjunto: [:medio] y [medio:].
• Consejo de depuración: imprime la lista en cada retorno de merge_sort con una sangría proporcional a la profundidad. Verás el árbol del apartado 4 dibujarse solo, y localizarás en qué mezcla se torció el resultado.

Traza merge(["18:03", "18:31", "18:44"], ["18:03", "18:12"]) paso a paso: tabla con i, j, comparación, elemento copiado. Los dos "18:03" provienen de líneas distintas (el de la primera lista iba antes en el panel original): comprueba que la estabilidad se respeta y señala la comparación exacta donde el <= marca la diferencia.

¿Cuántos niveles de mezcla tiene merge sort con n = 1.024 llegadas? ¿Y cuántas copias de elementos se hacen en total (aprox.)? Con esas cifras, explica en una frase por qué duplicar n (1.024 → 2.048) apenas duplica el tiempo total, mientras que en la inserción lo cuadruplicaría.

Escribe merge_k(listas) que mezcle k paneles ya ordenados (uno por línea de RutaBus) en un único listado ordenado, mezclándolos de dos en dos como en un torneo: mezcla los paneles por parejas, luego las parejas de resultados, etc. Razona su complejidad en función de n (total de elementos) y k. Pista: es el mismo argumento de niveles del apartado 5.

Solución 1

Resultado: ["18:03", "18:03", "18:12", "18:31", "18:44"]. La comparación del paso 1 es la decisiva: con <=, el empate lo gana la izquierda (el elemento que precedía en el panel original) y la estabilidad se conserva; con < se habría copiado primero el de la derecha, invirtiendo los empates.

Solución 2

1.024 = 2¹⁰ → 10 niveles de mezcla. Cada nivel copia los 1.024 elementos una vez → ≈ 10 × 1.024 = 10.240 copias (más las comparaciones, del mismo orden). Al duplicar a n = 2.048 hay 11 niveles × 2.048 ≈ 22.500: apenas 2,2×. En la inserción el coste promedio n²/4 pasa de ≈ 262.000 a ≈ 1.048.000: 4×. Es la diferencia entre crecer como n log n (el factor log casi no se mueve) y como n² (duplicar la entrada cuadruplica el trabajo) — la jerarquía de 01-03 en números concretos.

Solución 3

Análisis por niveles: cada ronda mezcla todos los elementos una vez → O(n) por ronda; el número de paneles se reduce a la mitad en cada ronda → log₂ k rondas. Total: O(n log k). Es el mismo teorema de niveles del apartado 5 con k en el papel de n. La alternativa ingenua (mezclar el panel 1 con el 2, el resultado con el 3, etc.) recorre los primeros elementos una y otra vez: O(n·k) — mezclar en torneo es a mezclar en cadena lo que merge sort es a la inserción.

Merge sort es divide y vencerás en estado puro: cortar por la mitad, ordenar recursivamente y mezclar con dos punteros en O(n). Hemos saldado la recurrencia pendiente desde 03-01 — T(n) = 2·T(n/2) + O(n) = Θ(n log n), porque cada uno de los log n niveles cuesta exactamente n — y hemos visto que esa cota se cumple siempre: mejor, peor y promedio, la garantía incondicional que la inserción no podía dar. A cambio paga O(n) de memoria auxiliar — el trade-off tiempo ↔ espacio de 02-02 — y renuncia a aprovechar el desorden pequeño, aunque Timsort demuestra que inserción y mezcla se alían de maravilla, y la ordenación externa lo corona como el algoritmo de los datos que no caben en memoria. Queda una pregunta abierta: ¿se puede tener O(n log n) sin pagar la memoria extra? La respuesta es el algoritmo más famoso — y más traicionero — de todos: quick sort, donde el trabajo no se hace al combinar sino al dividir, y donde por fin cobraremos la promesa de 02-03 sobre la brecha entre el caso promedio y el peor caso.