- Parte in fusione
- Confrontate
- Riscritte
- Già fuse
Merge sort
Il merge sort è un algoritmo divide et impera. Divide la lista a metà, ordina ciascuna metà allo stesso modo e fonde le due metà ordinate prendendo ogni volta il valore in testa più piccolo. Guarda le metà che passano in una riga di buffer e tornano in ordine, a qualsiasi velocità o un passo alla volta, e conta confronti, scritture e fusioni. Premi Avvia per guardare l'ordinamento, oppure Passo e Indietro per procedere un passo alla volta. Trascina il cursore dei passi per saltare in qualsiasi punto. I riquadri contano confronti, scritture nella lista e fusioni. Scegli quante barre usare, come partono, oppure inserisci i tuoi numeri. Con l'area selezionata, i tasti freccia avanzano di un passo, la barra spaziatrice avvia e mette in pausa, e Home e Fine saltano all'inizio e alla fine.
Come funziona
- Scegli quante barre usare e come partono: casuali, quasi ordinate, in ordine inverso o con pochi valori distinti. Oppure inserisci i tuoi numeri.
- Premi Avvia, oppure usa Passo e Indietro per procedere un passo alla volta. Trascina il cursore dei passi per saltare in qualsiasi punto dell'ordinamento.
- Guarda ogni fusione: le due metà ordinate scendono nel buffer, e il valore in testa più piccolo risale, uno alla volta.
Come funziona il merge sort
Un singolo valore è già ordinato. Per qualsiasi lista più lunga, dividila in due metà e ordina ciascuna metà con il merge sort. Poi fondile: guarda il valore in testa di ciascuna metà, sposta il più piccolo nel risultato e ripeti finché entrambe le metà sono vuote. Dato che entrambe le metà sono ordinate, anche il risultato lo è.
Sempre n log n
Dividere a metà più e più volte dà circa log₂ n livelli, e ogni livello di fusioni scrive ogni valore una volta, quindi l'ordinamento fa circa n log₂ n scritture e al massimo altrettanti confronti. A differenza di bubble sort, selection sort e insertion sort, questo non cresce come n², e l'ordine della lista conta molto meno. Il prezzo è un buffer lungo quanto la lista. Il merge sort è anche stabile, ed è per questo che è alla base degli ordinamenti di Python e Java.
Domande frequenti
Come funziona il merge sort?
Divide la lista a metà, ordina ciascuna metà con il merge sort e fonde le due metà ordinate prendendo ogni volta il più piccolo dei loro valori in testa. Una lista di un solo valore è già ordinata, quindi la divisione si ferma lì.
Quanti confronti fa il merge sort?
Con n valori, al massimo circa n log₂ n − n + 1 e almeno circa la metà di n log₂ n. Con 40 valori sono al massimo 177. Le scritture nella lista sono sempre le stesse per un dato n: una per valore a ogni livello di fusione.
Perché il merge sort ha bisogno di memoria aggiuntiva?
Fondere due metà sul posto è difficile da fare in modo rapido, quindi il merge sort classico copia le metà in un buffer e le riscrive in ordine. Il buffer è lungo quanto la lista: è il principale svantaggio rispetto a quicksort e heap sort.
Il merge sort è stabile?
Sì. Quando i due valori in testa sono uguali, va per primo quello della metà sinistra, così i valori uguali mantengono il loro ordine originale.
I miei numeri vengono inviati da qualche parte?
No. L'ordinamento avviene nel tuo browser, e le tue ultime impostazioni restano nella memoria locale di questo browser.
Pronto a provarlo?
Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.
Vai all'editor