L'ordenació per inserció (04-02) toca sostre en Θ(n²) perquè mou els elements d'un en un. Per trencar aquesta barrera aplicarem, per fi en la seva forma pura, l'estratègia de 03-01: merge sort és el fill directe de divideix i venceràs — divideix la llista en dues meitats, les ordena recursivament i les mescla. Tot el seu enginy viu en aquesta mescla: combinar dues llistes ja ordenades en una de sola costa només O(n). En aquesta lliçó construirem primer la funció merge, després l'algorisme complet, el traçarem sobre vuit arribades de RutaBus amb l'arbre de divisió i mescla, i saldarem el deute més antic del curs: resoldre amb rigor la recurrència T(n) = 2·T(n/2) + O(n) que vam deixar anotada a 03-01. Tancarem amb els seus costos (estable, però no in situ) i els seus usos reals, de l'ordenació de fitxers gegants al Timsort de Python.

1. La idea: la feina es fa en combinar
2. La funció merge: dos punters sobre dues llistes ordenades
3. Implementació completa de merge sort
4. Traça: l'arbre de divisió i mescla amb 8 arribades
5. La recurrència T(n) = 2·T(n/2) + O(n), resolta per nivells
6. Estabilitat i cost espacial: el preu de l'O(n log n)
7. Merge sort al món real: ordenació externa i Timsort

Recordem l'esquema de 03-01 — dividir, conquerir, combinar — i apliquem-lo a l'ordenació:

1. Dividir: parteix la llista en dues meitats (trivial: un tall pel centre).
2. Conquerir: ordena cada meitat recursivament amb el mateix merge sort. Cas base: una llista de 0 o 1 elements ja està ordenada.
3. Combinar: mescla les dues meitats ordenades en una sola llista ordenada.

Fixa't on viu la intel·ligència: dividir és un tall ximple i conquerir és delegar en la recursió. Tot el suc és al pas 3. Aquesta distribució de l'esforç — dividir barat, combinar feixuc — és el tret d'identitat de merge sort; a la propera lliçó en veurem el mirall exacte (quick sort: dividir feixuc, combinar gratis).

Per què això pot batre la inserció? Perquè mesclar dues llistes ordenades de mida n/2 no requereix comparar tots amb tots: com que totes dues ja estan ordenades, n'hi ha prou amb un recorregut simultani. Aquest "n'hi ha prou amb un recorregut" és la mina d'or.

El problema auxiliar: donades dues llistes ja ordenades, produir una llista ordenada amb tots els seus elements. La tècnica s'anomena dels dos punters: un índex per llista, i a cada pas es copia el menor dels dos candidats.

Pensa en dues piles de fitxatges de la L1 i la L2, cadascuna ja ordenada per hora, que cal fusionar en un llistat únic: mires la fitxa superior de cada pila, passes la més primerenca al llistat, i repeteixes.

Punt per punt:

• Els dos punters només avancen: i recorre esq i j recorre dret, cadascun d'esquerra a dreta, sense recular mai. Cada comparació copia exactament un element al resultat, així que el bucle fa com a màxim len(esq) + len(dret) voltes: merge és O(n) en el total d'elements. Invariant: resultat conté, ordenats, tots els elements ja consumits, i tot el pendent és ≥ que el darrer copiat.
• <= en comptes de <: davant d'un empat copiem primer el de la llista esquerra — el que era abans a la llista original. Així els empats conserven el seu ordre relatiu: és el detall que farà estable el merge sort complet, igual que el > estricte ho era a la inserció (04-02).
• Les restes (extend): quan una llista s'esgota, l'altra pot tenir cua pendent; com que està ordenada i tots els seus elements són majors que el que ja s'ha copiat, s'afegeix en bloc.

Exemple directe amb dos panells ordenats:

Amb merge resolt, l'algorisme complet és curt — divideix i venceràs en estat pur, compareu-lo amb la plantilla de 03-01:

• El cas base talla la recursió en llistes de mida ≤ 1, que ja estan ordenades per definició. Sense ell, llista[:0] i les crides continuarien per sempre — l'error clàssic de 03-01.
• Els talls llista[:mig] i llista[mig:] copien les subllistes (cost ocult de Python, 02-01). És còmode però contribueix al cost espacial que analitzarem a l'apartat 6.
• A diferència d'ordena_insercio, aquesta versió retorna una llista nova en comptes de modificar l'original: estil funcional, més fàcil de raonar.

Ordenem les 8 arribades acumulades del panell de l'Estació Nord:

El procés dibuixa dues piràmides: una de divisió (cap avall) i una de mescla (cap amunt):

Lectura de l'arbre:

• Baixada (divisió): 8 → 4+4 → 2+2+2+2 → vuit fulles d'1 element. Amb n = 8 = 2³ hi ha exactament 3 nivells de divisió: log₂ 8, el recompte de nivells de 03-01.
• Pujada (mescla): les fulles es mesclen per parelles. Seguim-ne una: merge(["18:42"], ["18:07"]) → ["18:07", "18:42"]. Després merge(["18:07","18:42"], ["18:31","18:59"]) → ["18:07","18:31","18:42","18:59"]: els punters van saltant entre llistes (18:07 d'esq, 18:31 de dret, 18:42 d'esq...). La mescla final entrellaça dues meitats de 4.
• Cada nivell de mescla toca els 8 elements exactament una vegada: 4 merges de 2, després 2 merges de 4, després 1 merge de 8 — sempre 8 còpies per nivell. Guarda aquesta dada: és la clau de l'anàlisi.

A 03-01 vam escriure la recurrència i vam prometre resoldre-la aquí. Merge sort l'encarna literalment:

Mètode dels nivells (el de 03-01, ara amb tots els comptes). Despleguem l'arbre de crides i sumem la feina no recursiva (la mescla) nivell a nivell:

El patró que vam veure a la traça és general: cada nivell costa exactament c·n, perquè en baixar un nivell els subproblemes es dupliquen però la seva mida es redueix a la meitat — el producte no canvia. I el nombre de nivells és el de vegades que es pot partir n per la meitat: log₂ n (04-01 en deia "comptar meitats").

Deute saldat. I amb un extra: en merge sort aquest cost no depèn de l'entrada. La mescla recorre sempre les dues llistes completes, tant si el panell ja està ordenat, com invertit o aleatori:

Aquesta cantonada inferior esquerra és la garantia incondicional que l'anàlisi de pitjor cas (02-03) ens va ensenyar a valorar: merge sort és predictible com un rellotge. El preu: no aprofita les dades gairebé ordenades com la inserció (el seu millor cas també és n log n).

Per calibrar la victòria: amb n = 10.000 expedicions, la inserció fa de mitjana ≈ n²/4 = 25.000.000 d'operacions; merge sort, ≈ n·log₂ n ≈ 132.000. Gairebé 200 vegades menys.

Estabilitat: sí. El <= de merge garanteix que davant d'un empat es copia primer l'element de la meitat esquerra — el que precedia a la llista original. Com que això es compleix a cada mescla de cada nivell, l'ordre relatiu dels empats sobreviu fins al final. Merge sort ordena per hora un panell de tuples (hora, línia) sense desordenar els empats (l'exemple de 04-02).

Espai: O(n) auxiliar — no és in situ. Cada merge construeix una llista resultat nova, i els talls llista[:mig] copien. Amb l'anàlisi de 02-02: en el moment de la mescla final conviuen l'entrada i el resultat — Θ(n) de memòria extra —, més els O(log n) marcs de la pila de recursió (dominats per l'n anterior). Compareu-ho amb l'O(1) de la inserció:

És el trade-off temps ↔ espai de 02-02 en la seva versió de manual: merge sort compra velocitat garantida pagant memòria. (Existeixen variants in situ de merge sort, però són notòriament intricades i rares a la pràctica; la resposta habitual a "vull n log n sense memòria extra" és una altra: quick sort, a la propera lliçó.)

Ordenació externa. Suposa l'històric anual de fitxatges de RutaBus: 500 GB que no caben als 32 GB de RAM del servidor. Merge sort és l'únic dels nostres algorismes que hi treballa còmode, perquè merge només necessita llegir les llistes seqüencialment, de principi a fi:

1. Llegeix el fitxer en blocs que sí que càpiguen en RAM, ordena cada bloc (amb el que sigui) i escriu-lo a disc: obtens molts trams ordenats.
2. Mescla els trams llegint-los en paral·lel amb la tècnica de punters — cada fitxer es llegeix seqüencialment, que és just el que els discos fan ràpid — fins a deixar-ne un de sol.

Aquest esquema (external merge sort) és la base de com ordenen les bases de dades i els frameworks de big data quan les dades no caben en memòria.

Timsort: el cercle es tanca. El sorted() i el list.sort() de Python usen Timsort, un híbrid dissenyat el 2002 per a la mateixa Python que combina... les nostres dues darreres lliçons:

• Detecta runs: trams ja ordenats presents a les dades reals (els panells gairebé ordenats de 04-02), i els estén amb ordenació per inserció — aprofitant que en trams curts i gairebé ordenats és imbatible.
• Mescla els runs amb un merge afinat, mantenint l'estabilitat i la garantia O(n log n) del pitjor cas.

Resultat: O(n) sobre dades ja ordenades (herència de la inserció), O(n log n) garantit (herència del merge), i estable. Quan a 02-01 donàvem per fet que sorted costava O(n log n), era això el que hi havia a sota. Moralitat d'enginyeria: els algorismes "de llibre" no competeixen entre si, es combinen — cadascun cobrint el punt feble de l'altre.

• Oblidar el cas base (len(llista) <= 1): la recursió no acaba mai (RecursionError). És el primer punt a revisar en qualsevol divideix i venceràs, com ja vam avisar a 03-01.
• Oblidar les restes a merge: sense els extend finals, els elements de la llista no esgotada es perden. Símptoma: el resultat surt ordenat... però més curt que l'entrada. Comprova sempre len(resultat) == len(esq) + len(dret).
• Usar < en comptes de <= a merge: continua ordenant bé, però davant d'empats copia primer el de la dreta i trenca l'estabilitat — el mateix error silenciós que el >= de la inserció. Només un test amb claus duplicades ho detecta.
• mig mal calculat (len(llista) / 2 amb / retorna float i trenca l'slicing; o dividir en [:mig+1] i [mig:] duplica l'element central). El tall correcte és exhaustiu i disjunt: [:mig] i [mig:].
• Consell de depuració: imprimeix la llista a cada retorn de merge_sort amb un sagnat proporcional a la profunditat. Veuràs l'arbre de l'apartat 4 dibuixar-se sol, i localitzaràs en quina mescla es va torçar el resultat.

Traça merge(["18:03", "18:31", "18:44"], ["18:03", "18:12"]) pas a pas: taula amb i, j, comparació, element copiat. Els dos "18:03" provenen de línies diferents (el de la primera llista anava abans al panell original): comprova que l'estabilitat es respecta i assenyala la comparació exacta on el <= marca la diferència.

Quants nivells de mescla té merge sort amb n = 1.024 arribades? I quantes còpies d'elements es fan en total (aprox.)? Amb aquestes xifres, explica en una frase per què duplicar n (1.024 → 2.048) tot just duplica el temps total, mentre que a la inserció el quadruplicaria.

Escriu merge_k(llistes) que mescli k panells ja ordenats (un per línia de RutaBus) en un únic llistat ordenat, mesclant-los de dos en dos com en un torneig: mescla els panells per parelles, després les parelles de resultats, etc. Raona la seva complexitat en funció de n (total d'elements) i k. Pista: és el mateix argument de nivells de l'apartat 5.

Solució 1

Resultat: ["18:03", "18:03", "18:12", "18:31", "18:44"]. La comparació del pas 1 és la decisiva: amb <=, l'empat el guanya l'esquerra (l'element que precedia al panell original) i l'estabilitat es conserva; amb < s'hauria copiat primer el de la dreta, invertint els empats.

Solució 2

1.024 = 2¹⁰ → 10 nivells de mescla. Cada nivell copia els 1.024 elements una vegada → ≈ 10 × 1.024 = 10.240 còpies (més les comparacions, del mateix ordre). En duplicar a n = 2.048 hi ha 11 nivells × 2.048 ≈ 22.500: tot just 2,2×. A la inserció el cost mitjà n²/4 passa de ≈ 262.000 a ≈ 1.048.000: 4×. És la diferència entre créixer com n log n (el factor log gairebé no es mou) i com n² (duplicar l'entrada quadruplica la feina) — la jerarquia de 01-03 en números concrets.

Solució 3

Anàlisi per nivells: cada ronda mescla tots els elements una vegada → O(n) per ronda; el nombre de panells es redueix a la meitat a cada ronda → log₂ k rondes. Total: O(n log k). És el mateix teorema de nivells de l'apartat 5 amb k en el paper de n. L'alternativa ingènua (mesclar el panell 1 amb el 2, el resultat amb el 3, etc.) recorre els primers elements una vegada i una altra: O(n·k) — mesclar en torneig és a mesclar en cadena el que merge sort és a la inserció.

Merge sort és divideix i venceràs en estat pur: tallar per la meitat, ordenar recursivament i mesclar amb dos punters en O(n). Hem saldat la recurrència pendent des de 03-01 — T(n) = 2·T(n/2) + O(n) = Θ(n log n), perquè cadascun dels log n nivells costa exactament n — i hem vist que aquesta fita es compleix sempre: millor, pitjor i mitjà, la garantia incondicional que la inserció no podia donar. A canvi paga O(n) de memòria auxiliar — el trade-off temps ↔ espai de 02-02 — i renuncia a aprofitar el desordre petit, tot i que Timsort demostra que inserció i mescla s'alien de meravella, i l'ordenació externa el corona com l'algorisme de les dades que no caben en memòria. Queda una pregunta oberta: es pot tenir O(n log n) sense pagar la memòria extra? La resposta és l'algorisme més famós — i més traïdor — de tots: quick sort, on la feina no es fa en combinar sinó en dividir, i on per fi cobrarem la promesa de 02-03 sobre la bretxa entre el cas mitjà i el pitjor cas.