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 dunque un array confrontando gli elementi.
L’idea di base è il Divide et Impera tanto noto a noi italiani discendenti dagli imperatori.
Brevemente spiego il Divide et Impera.
Abbiamo un problemone, non sappiamo dove mettere mani, allora che si fa? Lo dividiamo (Divide), ricorsivamente, in parti sempre più piccole e poi risolviamo quelle (et Impera).
Bene ora parlo del 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 che richiama 2 volte se stesso e poi chiama una procedura ausiliaria merge(A,i,m,f) che ‘Impera’ sulle due parti.
E’ importante questa procedura perchè fa il lavorone 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 è terminate, quindi 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 leggibile e che non servano molti commenti.
Analizzando la complessità dell’algoritmo, Merge sort, si vede che l’equazione di ricorrenza:
T(n) = 2T(n/2) + O(n)
questo perchè 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 i secondo caso del Teorema Master (collegamento Wikipedia), si ha che la complessità temporale del Merge Sort è
O(nlogn)
Mi auguro che per chiunque di voi che cercava una piccola delucidazione su questo utile algoritmo questo articolo sia stato utile.
Spero che questa sezioni di Algoritmi migliori!
Ad Maiora.
Potete consultare l'originaleQUI