Merge sort
Template:Stub informatica Il merge sort è un algoritmo di ordinamento 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.
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.
Implementazioni
Seguono alcune implementazioni in vari linguaggi.
void Sort(float array[], int begin, int end)
{
int mid;
if (end - begin <= 0) return;
mid = (begin + end) / 2;
Sort(array, begin, mid);
Sort(array, mid+1, end);
Merge(array, begin, mid, end);
}