Merge sort: differenze tra le versioni

Versione delle 23:20, 20 apr 2013

Versione delle 17:45, 20 ago 2013

Riga 1:

{{F|informatica|aprile 2012}}

{{Infobox Algoritmo

|class=[[Algoritmo di ordinamento]]

|image=[[Image:Merge sort animation2.gif|none|300px|Esempio di merge sort con una lista di numeri casuali.]]

Riga 23:

=== Esempio di funzionamento ===

[[Immagine: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

[10 3] [15 2] [1 4] [9 0]

Riga 96:

<math>T(n) = 2T\left(\frac{n}{2}\right)+ \Theta(n)</math>

la cui soluzione in forma chiusa è <math>\Theta(n \log n)</math>, per il secondo caso del [[Teorema_principale_Teorema principale (informatica)|teorema principale]].

Esistono implementazioni più efficienti della procedura merge, che hanno nel caso migliore complessità <math>O(1)</math>. Infatti, se i due array da fondere sono già ordinati, è sufficiente confrontare l'ultimo elemento del primo array con il primo elemento del secondo array per sapere che si può fonderli senza effettuare ulteriori confronti. Per cui si può implementare l'algoritmo mergesort in modo che abbia complessità O(nlogn) nel caso peggiore, e O(n) nel caso migliore, cioè quando l'array è già ordinato.

Riga 104:

{{Ordinamento}}

[[Categoria:Algoritmi di ordinamento]]