Merge sort: differenze tra le versioni

Versione delle 17:23, 23 lug 2008

Versione delle 08:41, 27 set 2008

Riga 1:

{{S|informatica}}

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]] [[algoritmo di ordinamento|di ordinamento]] molto intuitivo e abbastanza rapido, che utilizza un processo di risoluzione ricorsivo.