| Merge sort | |
|---|---|
 | |
| Classe | Algoritmo di ordinamento |
| Struttura dati | Array |
| Caso peggiore temporalmente | |
| Caso ottimo temporalmente | |
| Caso medio temporalmente | |
| Caso peggiore spazialmente | |
| Ottimale | In alcuni casi |
| Manuale | |
Ilmerge sort è unalgoritmo di ordinamento basato su confronti che utilizza un processo di risoluzionericorsivo, sfruttando la tecnica delDivide et Impera, che consiste nella suddivisione del problema in sottoproblemi della stessa natura di dimensione via via più piccola. Fu inventato daJohn von Neumann nel1945. Una descrizione dettagliata e un'analisi della versione bottom-up dell'algoritmo apparve in un articolo di Goldstine e Neumann già nel 1948.
Concettualmente, l'algoritmo funziona nel seguente modo:
Supponendo di dover ordinare la sequenza [10 3 15 2 1 4 9 0], l'algoritmo procede ricorsivamente dividendola in metà successive, fino ad arrivare agli elementi
[10][3][15][2][1][4][9][0]
A questo punto si fondono (merge) in maniera ordinata gli elementi, riunendoli in coppie:
[3 10][2 15][1 4][0 9]
Al passo successivo, si fondono le coppie di array di due elementi:
[2 3 10 15][0 1 4 9]
Infine, fondendo le due sequenze di quattro elementi, si ottiene la sequenza ordinata:
[0 1 2 3 4 9 10 15]
L'esecuzione ricorsiva all'interno del calcolatore non avviene nell'ordine descritto sopra. Tuttavia, si è formulato l'esempio in questo modo per renderlo più comprensibile.
L'algoritmo può essere implementato fondamentalmente tramite due tecniche:
Una possibile implementazione dell'algoritmo in forma dipseudocodice tramite una tecnica top-down è la seguente:
function mergesort (a[], left, right)if left < rightthen center ← (left + right) / 2 mergesort(a, left, center) mergesort(a, center+1, right) merge(a, left, center, right)
Una possibile implementazione della funzione merge (unione di due sottosequenze ordinate) è la seguente:
function merge (a[], left, center, right) i ← left j ← center + 1 k ← 0 b ← array temp size= right-left+1while i ≤ centerand j ≤ rightdoif a[i] ≤ a[j]then b[k] ← a[i] i ← i + 1 k ← k + 1else b[k] ← a[j] j ← j + 1 k ← k + 1end whilewhile i ≤ centerdo b[k] ← a[i] i ← i + 1 k ← k + 1end whilewhile j ≤ rightdo b[k] ← a[j] j ← j + 1 k ← k + 1end whilefor k ← leftto rightdo a[k] ← b[k-left]
L'algoritmo Merge Sort, per ordinare una sequenza di oggetti, ha complessità temporale sia nel caso medio che nel caso pessimo. Infatti:
Da questo segue che il tempo di esecuzione dell'algoritmo è dato dalla ricorrenza:
la cui soluzione in forma chiusa è, per il secondo caso delteorema principale.
Esistono implementazioni più efficienti della procedura merge, che hanno nel caso migliore complessità. Infatti, se i due array da fondere sono già ordinati, è sufficiente confrontare l'ultimo elemento del primo array con il primo elemento del secondo array per sapere che si può fonderli senza effettuare ulteriori confronti. Per cui si può implementare l'algoritmo mergesort in modo che abbia complessità O(nlogn) nel caso peggiore, e O(n) nel caso migliore, cioè quando l'array è già ordinato.
Altri progetti
Wikibooks contiene implementazioni delmerge sort
Wikimedia Commons contiene immagini o altri file sulmerge sort
| Algoritmi di ordinamento | ||
|---|---|---|
| Teoria | Teoria della complessità computazionale ·Notazione O Grande ·Array ·Lista ·Stack ·Coda ·Ordinamento comparativo ·Ordinamento adattivo |  |
| Algoritmi a scambio | Bubble sort ·Shaker sort ·Odd-even sort ·Comb sort ·Gnome sort ·Quicksort | |
| Algoritmi di selezione | Selection sort ·Heap sort ·Smoothsort | |
| Algoritmi ad inserimento | Insertion sort ·Shell sort ·Tree sort ·Library sort ·Patience sorting | |
| Algoritmi a fusione | Merge sort ·Timsort | |
| Algoritmi non comparativi | Radix sort ·Bucket sort ·Counting sort ·Pigeonhole sort | |
| Altri algoritmi | Rete di ordinamento ·Ordinamento topologico ·Ordinamento bitonico ·Ordinamento delle frittelle | |
| Algoritmi inefficienti | Stupid sort ·Trippel sort | |
