Merge sort: differenze tra le versioni

Versione delle 14:42, 9 dic 2008

Versione delle 11:33, 2 feb 2009

Riga 56:

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.

== Modalità di implementazione ==

Esistono vari tipi di implementazione del mergesort.

=== Metodo Top-Down ===

Corrisponde a quello presentanto in questa pagina, che opera da un insieme A e lo divide in sotto insiemi (A1, A2) fino ad arrivare all'unità per poi riunire le parti scomposte

=== Metodo Bottom-Up ===

Consiste nel considerare l'insieme A come composto da un vettore di n sequenze. Ad ogni passo fondo insieme due sequenze.

Riproponendo l'esempio sopra la sequenza dei passi diventa:

10 3 15 2 1 4 9 0

Primo passo, ho n sequenze distinte

10

3

15

2

1

4

9

0

Secondo passo, unisco le sequenze due a due

3 10

2 15

1 2

9 4

0

Terzo passo, continuo ad unire le sequenze due a due

2 3 10 15

1 2 4 9

0

Ho ancora più di una sequenza diversa, quindi continuo ad unire

1 2 2 3 4 9 10 15

0

0 1 2 2 3 4 9 10 15

A questo punto è rimasta una sola sequenza che è quella finale

==[[Pseudocodice]]==