Informatica I - ordinamento per fusione MergeSort

Algoritmo di ordinamento per fusione (MergeSort)

Presentiamo ora un algoritmo di ordinamento "per fusione" (MergeSort) che vedremo avere prestazioni migliori di quelle dell’ordinamento per selezione. Dovendo ordinare questo array, lo dividiamo in due parti (circa) uguali.

Fasi dell'ordinamento per fusione

• Dividiamo l'array in due parti (circa) uguali.
• Ordiniamo ciascuna delle due parti, separatamente.
• Uniamo le due parti ora ordinate in una fase chiamata fusione (merge).

Questa ultima fase si chiama fusione. Ora è facile costruire l'array ordinato, prendendo sempre il primo elemento da uno dei due sotto-array, scegliendo il più piccolo.

Situazione particolare

C'è una situazione in cui le due parti sono sicuramente ordinate: quando contengono un solo elemento.

MergeSort: Algoritmo ricorsivo

Si delinea quindi un algoritmo ricorsivo per ordinare un array, chiamato MergeSort:

Caso base

Se l’array contiene meno di due elementi, è già ordinato.

Passi da seguire

• Si divide l’array in due parti (circa) uguali.
• Si ordina la prima parte usando MergeSort.
• Si ordina la seconda parte usando MergeSort.
• Si fondono le due parti ordinate usando l’algoritmo di fusione (merge).