4.02 Merge Sort

Merge Sort

L'algoritmo è basato sui confronti: divide l'intero insieme di dati in gruppi di massimo due elementi. Confronta questo numero uno alla volta, ponendo il più piccolo alla sinistra della coppia.

Una volta che tutte le coppie sono ordinate confronta gli elementi più a sinistra con le due coppie a sinistra, creando un gruppo ordinato di quattro elementi con gli elementi più piccoli a sinistra ed i più grandi a destra.

Questo procedimento viene ripetuto finché non rimane un solo insieme, o gruppo.

Analisi

Siccome l'algoritmo divide i dati da confrontare ad ogni iterazione, ha un tempo di esecuzione linearitmico. Anche nel caso peggiore garantisce lo stesso tempo: O(n log n).