Merge sort
Il merge sort trasforma un problema difficile in tanti problemi facili: due liste ordinate sono semplici da unire in una sola. Dividi la lista a metà finché ogni pezzo è un singolo valore, poi fondi di nuovo i pezzi. È il classico algoritmo divide et impera, e il suo tempo è n log n qualunque sia l'input.
L'idea
Fondere è la parte facile. Date due liste ciascuna già ordinata, confronta i loro primi valori e prendi il più piccolo. Confronta i nuovi primi valori e prendi di nuovo il più piccolo. Quando una lista finisce, aggiungi il resto dell'altra. Ogni passo prende un valore, quindi fondere due liste di lunghezza totale m richiede al massimo m − 1 confronti. Il merge sort sfrutta questo per ordinare: dividi la lista a metà, ordina ciascuna metà con il merge sort e fondi le due metà.
Un esempio
Prendi 5, 1, 4, 2, 8. Dividila in 5, 1 e 4, 2, 8. La prima metà si divide in 5 e 1, che si fondono in 1, 5. La seconda metà si divide in 4 e 2, 8; il 2, 8 nasce dalla fusione di 2 e 8, poi si fonde con 4 in 2, 4, 8. Infine 1, 5 e 2, 4, 8 si fondono: 1, poi 2, poi 4, poi 5, e resta 8. In tutto sono 8 confronti, 12 scritture e 4 fusioni.
Perché n log n
Ogni divisione dimezza i pezzi, quindi dopo circa log₂ n livelli ogni pezzo è un singolo valore. Risalendo, ogni livello di fusioni tratta ogni valore una volta: n scritture e meno di n confronti per livello. In totale sono circa n log₂ n. Con 40 valori l'ordinamento fa 216 scritture e al massimo 177 confronti; il bubble sort può richiedere 780 confronti per la stessa lista. L'ordine dell'input conta molto meno che per quegli ordinamenti: con 40 valori, una lista ordinata richiede 100 confronti, una inversa 116 e una casuale circa 160.
Il buffer e la stabilità
Per fondere due metà vicine nella lista, il metodo classico le copia in un buffer e le riscrive in ordine. L'app mostra quel buffer come seconda riga di barre. Serve tanta memoria aggiuntiva quanto la lista, ed è il costo principale del merge sort. In cambio l'ordinamento è stabile: quando i due valori in testa sono uguali, va per primo quello della metà sinistra, così i valori uguali mantengono il loro ordine. La stabilità conta quando si ordinano record per un campo dopo l'altro.
Storia e utilizzo
John von Neumann descrisse il merge sort nel 1945, il che lo rende uno dei primi algoritmi scritti per un computer a programma memorizzato. Poiché legge e scrive i dati in lunghe sequenze, era il metodo standard per ordinare dati su nastro ed è ancora usato per file troppo grandi per la memoria. Timsort, usato da Python e da Java per gli oggetti, è un merge sort che prima cerca le sequenze già ordinate e usa l'insertion sort per i pezzi brevi.
Esploralo
Apri l'app e premi Passo. La parte ombreggiata della lista è quella che viene divisa o fusa, e la linea tratteggiata ne segna la metà. Quando inizia una fusione, entrambe le metà scendono nella riga del buffer; i due valori in testa vengono confrontati e il più piccolo risale. Guarda i contatori: le scritture sono le stesse per ogni lista della stessa lunghezza, e i confronti sono minimi per una lista ordinata o inversa e massimi per una casuale, ma mai più di circa n log₂ n.
Domande frequenti
Qual è la complessità temporale del merge sort?
O(n log n) nel caso migliore, medio e peggiore. La versione classica richiede O(n) di memoria aggiuntiva per il buffer.
Qual è la differenza tra merge sort e quicksort?
Entrambi dividono la lista e ordinano le parti. Il merge sort divide a metà senza guardare i valori e fa il suo lavoro durante la fusione; il quicksort fa il suo lavoro durante la divisione, spostando i valori attorno a un pivot, e non ha bisogno di fusione. Il quicksort ordina sul posto ed è spesso più veloce nella pratica, ma su input sfavorevoli può rallentare fino a n² e non è stabile. Il merge sort è sempre n log n e stabile.
Cos'è il merge sort bottom-up?
Una versione senza ricorsione: prima fonde i singoli valori vicini in coppie, poi le coppie in gruppi di quattro e così via, raddoppiando la lunghezza a ogni giro. Fa lo stesso lavoro della versione top-down mostrata qui.
Il merge sort è stabile?
Sì, purché a parità si prenda prima il valore della metà sinistra, come fa questa app.
Pronto a provarlo?
Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.
Prova il merge sort