Merge sort
Merge sort è un esperimento interattivo di Algoritmi in azione, una simulazione gratuita di StudyFi Lab che funziona direttamente nel browser.
Il merge sort divide l’array a metà, ordina ciascuna metà allo stesso modo (ricorsione) e poi fonde le due metà ordinate: prende sempre il più piccolo dei due elementi in testa. Dimezzare dà log₂ n livelli e ogni livello elabora tutti gli n elementi, quindi il tempo è sempre O(n log n). In caso di parità prende l’elemento di sinistra, perciò è stabile.
Prova questo: Prova un array invertito e poi uno quasi ordinato della stessa dimensione. I confronti cambiano appena: l’ordine dell’input conta poco.
Domande frequenti
Che cosa mostra l’esperimento «Merge sort»?
Il merge sort divide l’array a metà, ordina ciascuna metà allo stesso modo (ricorsione) e poi fonde le due metà ordinate: prende sempre il più piccolo dei due elementi in testa. Dimezzare dà log₂ n livelli e ogni livello elabora tutti gli n elementi, quindi il tempo è sempre O(n log n). In caso di parità prende l’elemento di sinistra, perciò è stabile.
Come provo «Merge sort»?
Prova un array invertito e poi uno quasi ordinato della stessa dimensione. I confronti cambiano appena: l’ordine dell’input conta poco.
Studi per una verifica?
Carica i tuoi appunti e StudyFi li trasforma in flashcard, test e podcast.