Traccia dell'esercizio in allegato.
Ecco la mia risposta e spero sia corretta.
L'algoritmo Merge Sort è un algoritmo di ordinamento, o anche un algoritmo di Ordinamento per Fusione.
Merge Sort, riesce ad ordinare (per fusione) un array suddividendolo in due sottoarray di eguale dimensione, ordinando ognuno di essi e fondendoli in un array più grande.
Un caso di esempio base è un Array con un solo elemento, che naturalmente è ordinato, per cui l'ordinamento per fusione è immediato, in quanto l'ordinamento per fusione torna immediato quando viene chiamato con un Array di un solo elemento(passo ricorsivo).
Il passo di ricorsione suddivide un Array di due o più elementi in due sottoarray di eguale misura, ordina ricorsivamente ogni sottoarray, quindi li fonde in un terzo array ordinato e più grande.
Esempio.
Array A:
4 10 34 56 77
Array B:
5 30 51 52 93
L'ordinamento per fusione combina questi due array in un terzo array C più grande (ottenuto per fusione)
Passo 1: 4 < 5
Array C:
4 .......
Passo 2: 10 > 5
Array C:
4 5 ....
Passo 3: 10 < 30
Array C:
4 5 10 .......
e così via....
Complessità computazionale:
Migliore Intermedio Peggiore
Merge Sort n log n n log n n log n
Cosa ne dite
Allegati:
31893_f57c1ce19319e5b89d9aa4abdc59160a.jpg