Merge sort: differenze tra le versioni

Versione delle 20:22, 27 nov 2017

Versione delle 09:10, 3 dic 2017

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 (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.