Merge sort: differenze tra le versioni

Versione delle 11:00, 22 giu 2007

Versione delle 11:06, 22 giu 2007

Riga 3:

L'idea alla base del merge sort è il procedimento [[Divide et impera (informatica)|Divide et Impera]], che consiste nella suddivisione del problema in sottoproblemi via via più piccoli.

==Fase 1: 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.

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.

Riga 12 ⟶ 8:

L'algoritmo fu inventato da [[John von Neumann]] nel [[1945]].

==Fase 1: 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 <math>\mathit{A}</math>

==Esempio pratico==