Merge sort: differenze tra le versioni

Versione delle 22:25, 17 set 2013

Versione delle 11:10, 4 ott 2013

Riga 12:

}}

Il '''merge sort''' è un [[algoritmo]] [[algoritmo di ordinamento|di ordinamento]] basato su confronti che utilizza un processo di risoluzione [[Algoritmo ricorsivo|ricorsivo]], sfruttando la tecnica del [[Divide et impera (informatica)|Divide et Impera]], che consiste nella suddivisione del problema in sottoproblemi della stessa natura di dimensione via via più piccola. Fu inventato da [[John von Neumann]] nel [[1945]]. Una descrizione dettagliata e un'analisi della versione bottom-up dell'algoritmo apparve in un articolo di Goldstine e Neumann già nel 1948.

== Descrizione dell'algoritmo ==

Riga 22:

=== Esempio di funzionamento ===

[[ImmagineFile:AnimazioneMergeSort.gif|thumb|492px|Simulazione del merge sort in esecuzione su di un array]]

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 alle coppie

Riga 33:

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:

Riga 57:

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 ← left

'''while''' i ≤ center '''and''' j ≤ right '''do'''

'''if''' a[i] ≤ a[j]

Riga 69:

'''else'''

b[k] ← a[j]

j ← j + 1

k ← k + 1

'''end while'''

'''while''' i ≤ center '''do'''

b[k] ← a[i]

Riga 78:

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]