Il Mergesort
Uno tra i migliori algoritmi di ordinamento è certamente quello chiamato mergesort (o anche MergeSort), più specificamente definito come algoritmo di ordinamento per fusione (la parola merge, in inglese, significa, appunto, fondere).
Perché affermiamo che questo algoritmo sia tra i migliori? Perché la sua complessità computazionale di ordinamento è O(n log n) anche nel caso pessimo.
Il mergesort è migliore, ad esempio, del quicksort, in quanto quest’ultimo, nel caso peggiore, ha complessità O(n^2), quasi come i peggiori algoritmi, mentre il mergesort mantiene sempre prestazioni ottimali.
Come funziona il Mergesort
Il principio di funzionamento del mergesort è molto semplice e, probabilmente, già noto nella pratica a chi ha dovuto ordinare decine o centinaia di elementi in maniera manuale.
Se, infatti, si devono ordinare molti elementi a mano, l’esperienza insegna che è più semplice dividerli in piccoli gruppi, ordinare ciascun gruppo e poi, dopo averli ordinati tutti e raggruppati in mucchietti ordinati, prendere l’elemento più piccolo sulla cima di uno dei mucchi, poi il nuovo più piccolo e via dicendo, fino ad esaurimento dei mucchietti. Il risultato sarà una pila di elementi ordinati.
Il mergesort, per questa sua caratteristica di suddividere in parti più piccole, è stato spesso usato per ordinare in quei casi in cui non era disponibile sufficiente memoria per l’ordinamento di tutto l’array. In tal caso lo si spezzava in parti più piccole che venivano ordinate in memoria e poi fuse assieme, in genere su disco.
Quello che vogliamo mostrare oggi è invece il suo utilizzo come algoritmo di ordinamento estremamente performante.
Il mergesort agisce applicando il principio divide et impera, ossia scomponendo ricorsivamente il problema in sotto-problemi sempre più semplici per poi ricomporne i risultati.
Nel nostro caso, l’algoritmo di mergesort si compone di due fasi di mergesort e una di merge.
Un esempio in Java di mergesort (il codice completo è disponibile in fondo a questo articolo) è il seguente:
// funzione ricorsiva di merge sort
public void mergeSort(int[] a, int p, int r) {
System.out.println(“Entrato in mergeSort p =” + p + “; r = ” + r);
// se la partizione è di un solo elemento ritorna al livello precedente
if (p == r) {
System.out.println(“p == r, si ritorna ” + p);
return;
}
// se la partizione ha più di un elemento …
// … la partiziona in due metà
int q = (int) Math.floor((p + r) / 2.0);
// ordina la prima sotto-partizione
mergeSort(a, p, q);
// ordina la seconda sotto-partizione
mergeSort(a, q + 1, r);
// le fonde insieme e ritorna al livello superiore
merge(a, p, q, r);
}
Quindi il mergesort divide l’array che gli arriva in due metà (ossia due partizioni) e su ciascuna applica … il mergesort!
Quando si ritrova con una metà che consiste in un solo elemento, allora ritorna e, quando ha due metà di un elemento, ne effettua il merge, ossia fonde insieme, come spiegato sopra con i mucchietti, le due partizioni.
Ordinate le due partizioni con un singolo elemento, ritorna al livello di ricorsione precedente e lo chiude con lo stesso meccanismo, fino ad aver ordinato e fuso tutte le partizioni rimaste in sospeso.
Il processo di merge
Cuore dell’algoritmo è il processo di merge. Per tale fusione utilizzeremo un array ausiliario b, in cui copieremo i dati via via estratti dai mucchietti (ossia b è la nostra pila di dati ordinati).
Il codice Java (anche qui l’esempio completo è in fondo all’articolo):
// metodo che esegue la fusione delle due partizioni dell’array a:
// prima partizione: elementi compresi tra p e q
// seconda partizione: elementi compresi tra q+1 e r
private void merge(int[] a, int p, int q, int r) {
System.out.println(“Entrato in merge p = ” + p + “; q = ” + q + “; r = ” + r);
// prepara alcune variabili
int i = p;
int k = p;
int j = q + 1;
// prepara l’array temporaneo dove fare il merge
int[] b = new int[r];
// finchè non ho esaurito una delle partizioni da fondere …
while ((i <= q) && (j <= r)) {
// se l’elemento della prima partizioneè il più piccolo mettilo in b …
if (a[i] < a[j]) {
b[k] = a[i];
// passa al prossimo della prima partizione
i++;
} else {
// … se invece il più piccolo è quello della seconda, mettici questo in b
b[k] = a[j];
// passa al prossimo della seconda partizione
j++;
}
// posizionati sul prossimo elemento di b
k++;
}
// variabile che contiene il numero di elementi da copiare
int lun;
// se la prima partizione non è stata esaurita nel merge (i.e. è finita prima la seconda) …
if (i <= q) {
// … copia i rimanenti in coda
lun = q – i + 1;
System.arraycopy(a, i, a, k, lun);
}
// copia tutti gli elementi di b all’inizio
lun = k – 1 – p + 1;
System.arraycopy(b, p, a, p, lun);
}
Il processo di merge è concettualmente semplice: si hanno solo due partizioni (due mucchietti), si sceglia via via il più piccolo da ogni mucchietto e lo si mette in b (ossia la pila ordinata). Quando si è finito uno dei due mucchietti si accoda l’altro.
Il codice completo del mergesort
Il codice Java completo del mergesort è disponibile nello zip al link seguente:
Dopo averlo scaricato e decompresso, lo potete caricare in qualsiasi IDE Java (ad esempio Eclipse o Netbeans) per poterlo eseguire.
Il codice non necessita di librerie Java particolari e gira con Java 7 o superiore.
Il codice è commentato in lingua italiana.