Merge sort: differenze tra le versioni

Versione delle 23:28, 12 gen 2015

Versione delle 20:09, 25 mar 2015

Riga 100:

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.

== Bibliografia ==

* {{cita libro| Thomas | Cormen | Introduction to Algorithms | ed=3 }}

== Altri progetti ==