Confronti
Scritture
Fusioni

  • Parte in fusione
  • Confrontate
  • Riscritte
  • Già fuse

Scopri di più sul merge sort

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

  1. Scegli quante barre usare e come partono: casuali, quasi ordinate, in ordine inverso o con pochi valori distinti. Oppure inserisci i tuoi numeri.
  2. 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.
  3. 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