=== 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

  • si inizializzano due indici,i e j, uno al primo elemento del primo vettore e l'altro al primo elemento del secondo vettore (si supponga che ogni vettore sia ordinato in senso crescente).
  • si inizializza un indice k al primo elemento del terzo vettore
  • finchè i e j sono entrambi all'interno dei rispettivi vettori, si confrontano gli elementi puntati e il più piccolo dei due viene copiato in posizione k del terzo vettore
  • si incrementa l'indice dell'elemento copiato e l'indice k
  • quando i o j escono dal rispettivo vettore si "svuotano" gli elementi del vettore il cui indice non ha ancora raggiunto l'estremo all'interno del terzo vettore
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:
  • si separa il vettore da ordinare in due parti uguali (o al massimo con un elemento di differenza se il vettore ha lunghezza dispari)
  • si ordinano (ricorsivamente) le due parti
  • si fondono le due parti per ottenere il vettore ordinato
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 ...

download-icon Main.c

Altro ...

download_icon Main.html