Merge Sort
Utilizza l'algoritmo di fusione su un array.
...
mergesort(dati, 0, dati.QUANTI-1)
...
PROCEDURA mergesort(IN/OUT REALE v[], INTERO inf, INTERO sup)
INIZIO
SE(inf < sup) ALLORA
INIZIO
INTERO medio=(inf+sup)/2
mergesort(v, inf , medio)
mergesort(v, medio+1, sup )
merge(v, inf, medio, sup)
FINE
FINE
mergesort(dati, 0, dati.QUANTI-1)
...
PROCEDURA mergesort(IN/OUT REALE v[], INTERO inf, INTERO sup)
INIZIO
SE(inf < sup) ALLORA
INIZIO
INTERO medio=(inf+sup)/2
mergesort(v, inf , medio)
mergesort(v, medio+1, sup )
merge(v, inf, medio, sup)
FINE
FINE
La chiamata chiede di ordinare l'array dal primo, 0, all'ultimo, n-1, elemento.
A ogni chiamata, dopo aver calcolato medio, si effettuano due chiamate ricorsive, da inf a medio e da medio+1 a sup.
In pratica le chiamate ricorsive scendono fino al livello di array con un solo elemento. Al ritorno delle chiamate si effettua la fusione delle due parti ordinate (l'array con un solo elemento è già ordinato...).
Esempio 1
Sia v={1, 3, 7, 4, 15, 0, 9, 10}
Gli indici inf e sup assumono i valori
(0..0)
(1..1)
(2..2)
(3..3)
(4..4)
(5..5)
(6..6)
(7..7)
A partire dai singoli elementi le fusioni ricostruiscono l'array ordinato
(0..0) {1}
(0..1) {1, 3}
(0..3) {1, 3, 4, 7}
(2..3) {4, 7}
(0..7) {0, 1, 3, 4, 7, 9, 10, 15}
(4..5) {0, 15}
(4..7) {0, 9, 10, 15}
(6..7) {9, 10}
Esempio 2
Sia v={1, 3, 7, 4, 15, 0, 9, 10, 8, 2}
Gli indici inf e sup assumono i valori
(0..0)
(1..1)
(2..2)
(3..3)
(4..4)
(5..5)
(6..6)
(7..7)
(8..8)
(9..9)
E le fusioni
(0..0) {1}
(0..1) {1, 3}
(0..2) {1, 3, 7}
(0..4) {1, 3, 4, 7, 15}
(3..4) {4, 15}
(0..9) {0, 1, 2, 3, 4, 7, 8, 9, 10, 15}
(5..6) {0, 9}
(5..7) {0, 9, 10}
(5..9) {0, 2, 8, 9, 10}
(8..9) {2, 8}
