Java Algoritmi Di Ordinamento: Merge Sort

Andiamo oggi ad analizzare uno tra i migliori algoritmi di ordinamento: il Merge Sort. Detto anche algoritmo per fusione, fa parte della famiglia dei Divide and Conquer proprio come il Quick Sort. A differenza del prima citato Quick Sort, il Merge Sort offre prestazioni migliori, siccome nella peggiore delle ipotesi la sua complessità rimane simile a O(n log n) mantenendo prestazioni ottimali.

L'unica pecca del Merge Sort è che necessita di strutture dati aggiuntive per poter svolgere le sue elaborazioni. Possiamo quindi dire che è un algoritmo stabile, ma non in-place. Inoltre è adattivo.

Funzionamento

Iniziamo guardando un'immagine esplicativa del funzionamento dell'algoritmo.

Il funzionamento potrebbe essere già noto a chi ha già avuto a che fare con grandi collezioni di dati da ordinare. L'idea alla base è quella di dividere l'array in gruppetti e ordinarli. Una volta finita l'operazione di ordinamento dei singoli sottoinsiemi si prende il più piccolo tra gli elementi dei vari gruppi e inserirlo nel nuovo array. Si itera quindi questo processo sino ad esaurimento dei "mucchietti".

Il problema fondamentale è la fusione.

Algoritmo di fusione

• Il semi-vettore sinistro è copiato su un vettore di appoggio;
• Si seleziona il minimo tra il vettore di appoggio e il semi-vettore di destra e lo si copia sul vettore finale;
• Si termina quando tutti gli elementi di appoggio sono stati copiati;

Implementazione

public class MergeSort 
{ 
    // Fonde due sottoarray di arr[]. 
    // il primo sottoarray è arr[l..m] 
    // il secondo sottoarray è arr[m+1..r] 
    public static void merge(int arr[], int l, int m, int r) { 
        // Trova le dimensioni dei due sottoarray da unire
        int n1 = m - l + 1; 
        int n2 = r - m; 

        /* Crea array temporanei */
        int L[] = new int [n1]; 
        int R[] = new int [n2]; 

        /*Copia i dati in array temporanei*/
        for (int index=0; index<n1; ++index) 
            L[index] = arr[l + i]; 
        for (int j=0; j<n2; ++j) 
            R[j] = arr[m + 1+ j]; 

        /* Unisce gli array temporanei */

        // Indici iniziali dei due array 
        int index = 0, j = 0; 

        // Indice iniziale del sottoarray finale
        int k = l; 
        while (index < n1 && j < n2){ 
            if (L[index] <= R[j]) { 
                arr[k] = L[index]; 
                index++; 
            } else{ 
                arr[k] = R[j]; 
                j++; 
            } 
            k++; 
        } 
        /* Copia gli elementi rimanenti di L[] se ce ne sono */
        while (i < n1) { 
            arr[k] = L; 
            index++; 
            k++; 
        } 

        /* Copia gli elementi rimanenti di R[] se ce ne sono */
        while (j < n2) { 
            arr[k] = R[j]; 
            j++; 
            k++; 
        } 
    } 

    // Funzione principale che ordina arr[l..r] usando 
    // merge() 
    public static void sort(int arr[], int l, int r) { 
        if (l < r) { 
            // Trova il punto medio 
            int m = (l+r)/2; 

            // Ordina la prima e la seconda metà
            sort(arr, l, m); 
            sort(arr , m+1, r); 

            // Unisce le due metà 
            merge(arr, l, m, r); 
        } 
    } 

    public static void main(String args[]) { 
        int arr[] = {12, 11, 13, 5, 6, 7}; 

        System.out.println("Array da ordinare"); 
        System.out.println(Arrays.toString(arr));

        MergeSort.sort(arr, 0, arr.length-1); 

        System.out.println("nArray ordinato"); 
        System.out.println(Arrays.toString(arr));
    } 
} 

Alessio Mungelli

Computer Science student at UniTo (University of Turin), Network specializtion, blogger and writer. I am a kind of expert in Java desktop developement with interests in AI and web developement. Unix lover (but not Windows hater). I am interested in Linux scripting. I am very inquisitive and I love learning new stuffs.