Merge sort
Prefazione:
Per comprendere il funzionamento del merge sort bisogna intuire il ragionamento che stà a monte di tale algoritmo, parliamo quindi prima del paradigma della ricorsione che definisce delle operazioni in modo ricorsivo che il calcolatore risolverà in qualche modo. Dato un programma(A,n) su n dati, tale programma giungerà alla riga di codice di un comando if tipo: if(guardia){com1} else {com2} (esempio in java) una specie di bivio dove uscirà se la guardia non soddisfa, eseguirà altrimenti. Nel secondo caso il {com2} indicherà di risolvere il problema soddividendolo in sottoproblemi più semplici, intuitivamente da Programma(A,1....n) a Programma(A,1....n/2)
Programma(A,n/2+1....n)
e per ogni sottoproblema si troveà una soluzione. Trovate quindi tutte le soluzioni si fonderanno assieme (merge)dando luogo alla soluzione finale.
Il merge sort è un algoritmo di ordinamento molto intuitivo e abbastanza rapido, che utilizza un processo di risoluzione ricorsivo.
L'idea alla base del merge sort è il procedimento Divide et Impera, che consiste nella suddivisione del problema in sottoproblemi via via più piccoli.
Il merge sort opera quindi dividendo l'insieme da ordinare in due metà e procedendo all'ordinamento delle medesime ricorsivamente. Quando si sono divise tutte le metà si procede alla loro fusione (merge appunto) costruendo un insieme ordinato.
L'algoritmo fu inventato da John von Neumann nel 1945.
Fase 1: Divide
L'insieme di elementi viene diviso in 2 metà. Se l'insieme è composto da un numero dispari di elementi, viene diviso in 2 sottogruppi dei quali il primo ha un elemento in meno del secondo.
Es. 11 => 5 e 6
Fase 2: Impera
Supponendo di avere due sequenze già ordinate. Per unirle, l'algoritmo mergesort estrae ripetutamente il minimo delle due sequenze in ingresso e lo pone in una sequenza in uscita.
Dati un array e due indici x ≤ y, denotiamo la porzione dell'array A costituita dagli elementi .
![{\displaystyle {\mathit {A[x;y]}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6519a83ca46d831f052be43c09fb0e81ced8eb72)
![{\displaystyle {\mathit {A[x]...A[y]}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1e46689cf161b16eecb91defa4e7692706d9b491)
Esempio pratico
Supponiamo di dover ordinare il seguente array:
10 3 15 2 1 4 9 0
Si procede dividendolo in metà successive, fino ad arrivare a coppie:
10 3 15 2 1 4 9 0
A questo punto si fondono (merge) in maniera ordinata gli elementi, riunendo le metà:
10 3 -> 3 10 15 2 -> 2 15 1 4 -> 1 4 9 0 -> 0 9
Al passo successivo:
3 10 2 15 -> 2 3 10 15 1 4 0 9 -> 0 1 4 9
Infine:
2 3 10 15 0 1 4 9 -> 0 1 2 3 4 9 10 15
L'esecuzione ricorsiva all'interno del calcolatore non avviene nell'ordine descritto sopra, ma si è preferito formulare l'esempio in questo modo in maniera da renderlo più comprensibile.
merge (a[], left, center, right)
i ← left
j ← center + 1
k ← 0
while ((i <= center) && (j <= right)) do
if (a[i] <= a[j]) then
b[k] ← a[i]
i ← i + 1
else
b[k] = a[j]
j ← j + 1
k ← k + 1
end while
while (i <= center) do
b[k] ← a[i]
i ← i + 1
k ← k + 1
end while
while (j <= right) do
b[k] ← a[j]
j ← j + 1
k ← k + 1
end while
for k ← left to right do
a[k] ← b[k - left]
mergesort (a[], left, right)
if (left < right) then
center ← (left + right) / 2
mergesort(a, left, center)
mergesort(a, center+1, right)
merge(a, left, center, right)
Analisi delle prestazioni
Il tempo di esecuzione dell'algoritmo Merge Sort è Θ(n log n). Infatti:
- la funzione merge ha costo Θ(n), e mergesort richiama se stessa due volte ogni volta su metà della porzione di input. Quindi possiamo associare al tempo di esecuzione di mergesort la funzione temporale
che per il secondo caso del teorema master è Θ(nlogn).
Altri progetti
Wikibooks contiene implementazioni di merge sort
Wikimedia Commons contiene immagini o altri file su merge sort
