Merge Sort

Vi segnalo un articolo del mio amico di Caratteri Sparsi riguardo l'algoritmo di ordinamento Merge Sort.

Potete consultare l'originale QUI.

Rappresentazione grafica dell'algoritmo

Il Merge Sort è un algoritmo di ordinamento abbastanza veloce basato su confronti.
Ordina infatti un array confrontando gli elementi e seguendo come idea base il Divide et Impera.

Spieghiamo brevemente il concetto di Divide et Impera.
Abbiamo un problemone da risolvere e non sappiamo dove mettere mani. Cosa si fa? Lo si divide (Divide), in maniera ricorsiva, in parti sempre più piccole per poi risolverle singolarmente (et Impera).

Bene, ora passiamo al MergeSort. Prendo un array non ordinato, lo divido in sotto-array sempre più piccoli e poi riunisco le parti.

Lo pseudocodice:

mergesort(array A, indice i, indice f){
   if (i <= f) then return
   m = (i+f)/2 //trovo l'indice centrale
   mergesort(A,i,m) //parte sinistra
   mergesort(a,m+1,f) //parte destra
   merge(A,i,m,f)
}

Si vede come il metodo richiami 2 volte se stesso per poi chiamare una procedura ausiliaria merge(A,i,m,f) che ‘Impera’ sulle due parti.
Questa procedura è importante perchè fa il "lavoro sporco" dell’algoritmo.
Essa controlla un elemento della prima parte con un elemento della seconda parte, vede qual è il più piccolo e lo ordina fino a che una delle due parti non è terminata. Infine concatena la restante parte non terminata.

Pseudocodice:

merge(A,i1,f1,f2){
   X[f2-i1+1] //array ausiliario
   i = 1
   i2 = f1 +1
   while( i1 <= f1 && i2 <= f2){
      if (A[i1] <= A[i2])[
         X[i] = A[i1]
         i1++
      }

      else{
         X[i] = A[i2]
         i2++
      }
   i++
   }
   if(i1 < f1) then copia A[i1,f1] in X
   else copia A[i2,f2] in X
   copia X in A[i1,f2]
}

Credo che lo pseudocodice sia abbastanza leggibile e che quindi non servano molti commenti.

Analizzando la complessità dell’algoritmo si può vedere l’equazione di ricorrenza:

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

richiama due volte se stesso con metà porzione e poi usa la procedura merge che costa O(n) perchè scorre al massimo tutto l’array una volta sola.

Dunque, per il secondo caso del Teorema Master (collegamento Wikipedia), si ha che la complessità temporale del Merge Sort è

O(nlogn)

Mi auguro che questo breve articolo sia stato utile per chiunque cercava una piccola delucidazione su questo utile algoritmo.
Ad Maiora.

Potete consultare l'originale QUI.