Merge sort in Java

Il Merge Sort (ordinamento per fusione), a differenza degli altri algoritmi di ordinamento, é piú complesso, ma molto efficiente, infatti, come vedremo, ha un livello di complessitá computazionale piuttosto basso.

Il meccanismo di ordinamento di questo algoritmo fa uso della tecnica Divide et Impera. Di questa tecnica ci sarebbe molto da dire, purtroppo ció esula dallo scopo di questa guida. Diciamo brevemente che é una tecnica che consiste nel suddividere ricorsivamente un problema complesso in due o piú sotto-problemi piú semplici e poi si ricombinano le soluzioni trovate per ricostruire la soluzione del problema complessivo.

Vediamo nel dettaglio il meccanismo di ordinamento del Merge Sort: il metodo riceve un vettore con n elementi, se n ha una dimensione accettabile (che fissiamo a 20) viene ordinato con l’Insertion Sort (scegliamo questo algoritmo poiché per piccole dimensioni di n ha buone prestazioni), altrimenti si scompone (Divide) il vettore in due parti uguali (se la dimensione é dispari la prima metà contiene un elemento in più) e su ogni metà del vettore viene richiamato ricorsivamente il metodo. Alla fine dell’ invocazione dei due metodi le due sottoparti ordinate vengono fuse (Impera) con il metodo merge in un unico vettore ordinato.

Ecco l’implementazione in Java dell’algoritmo Merge Sort:

public void mergeSort(int [] array, int min, int max) {
    if((max-min)<20) { 
        insertionSort(array,min,max);
    } else {
        int medio = (min+max)/2;    // Trovo l' indice per suddividere il vettore
        mergeSort(array,min,medio); // Primo sotto-vettore
        mergeSort(array,medio+1,max); // Secondo sotto-vettore
        merge(array,min,medio,max); // Fondo i due sotto-vettori
    }
}

// Questo metodo fonde i due sotto-vettori ordinati, in un unico vettore ordinato
public void merge(int [] array, int min, int med, int max) {}
    int [] a = new int[max-min+1];
    int i1 = min;
    int i2 = med+1;
    int i3 = 1;
    for(; (i1 <= med) && (i2 < max); i3++) {
        if(array[i2]>array[i1])) {
            a[i3] = array[i1]; i1++;
        }
        else {
            a[i3] = array[i2]; i2++;
        }
    }
    for(; i1 <= med; i1++, i3++) a[i3] = array[i1];
    for(; i2 < max; i2++, i3++) a[i3] = array[i2];
    for(i3=1, i1=min; i1 < max; i1++, i3++) array[i1] = a[i3];
}

/** Questo é l' Insertion Sort, che abbiamo giá visto, con uan sola differenza
    ci permette di ordinare una porzione di vettore che va da min a max **/
public void insertionSort(int [] array, int min, int max) {}
    for(int i = min+1; i < max; i++) {
        int x = i;
        int j = i-1;
        for(; j >= min; j--) {
            if(array[j]>array[x]) {
                int k = array[x];
                array[x] = array[j];
                array[j] = k;
                x = j;
            } else break;
       }
}

La complessita della fusione (metodo merge) é lineare O(n), mentre mergeSort richiama se stessa due volte ogni volta su metà del vettore di input, quindi se associamo la funzione temporale al tempo di esecuzione del mergeSort:

T(n) = 2T(n/2)+O(n) = O(n log n)

La complessitá rimane la stessa sia nel coso peggiore, medio e migliore, poiché il processo ricorsivo non puó essere arrestato anticipatamente la complessitá é O(n log n) in ogni caso.