--Imparando.net--

Merge sort

L'algoritmo mergesort permette di ordinare un insieme di elementi in tempo nlogn, quindi appartiene alla stessa classe di complessità del quicksort.
Questo algoritmo sfrutta la velocità del merging di due vettori ordinati: è noto che avendo due vettori ordinati e dovendo unirli (merging) in modo da ottenere un terzo vettore ordinato, si può procedere nel seguente modo

Alla fine di questo procedimento otteniamo un terzo vettore ordinato e il costo per ottenerlo è stato di N+M, con N dimensione del primo vettore e M dimensione del secondo, quindi costo lineare. Il mergesort sfrutta questa operazione in questo semplice modo: Rispetto al merge, in questo caso si ha un solo vettore che è composto dalla prima metà ordinata e dalla seconda pure ordinata, al posto di avere due vettori distinti ordinati, per il resto il procedimento è lo stesso spiegato in precedenza. Si usa comunque un vettore ausiliaro dove copiare gli elementi uniti dal merge e quindi alla fine di ogni fusione è necessario ricopiare gli elementi nel vettore originario.

Filmato che mostra il funzionamento del mergesort attraverso una simpatica danza.

Sorgenti ...

Main.c

Altro ...

Main.html
Licenza Creative Commons
Didattica di Alessandro Bugatti è distribuito con Licenza Creative Commons Attribuzione - Non commerciale - Non opere derivate 3.0 Unported.