Merge sort: differenze tra le versioni

Versione delle 09:09, 23 ott 2011

Versione delle 14:19, 29 ott 2011

Riga 161:

che per il secondo caso del [[teorema master]] è Θ(''n''log''n'').

La procedura Merge ha nel caso migliore complessità O(1), infatti se i due array da fondere sono già ordinati, basterà confrontare l' ultimo elemento del primo array con il primo elemento del secondo array per sapere che si può fonderli senza effettuare ulteriori confronti.

Da notare che questa complessità si mantiene tale in ogni caso, da quello migliore a quello peggiore, ed è questo uno dei punti di forza dell'algoritmo.

Altrimenti se gli array non sono ordinati la procedura Merge ha complessità O(n).

Per cui l' algoritmo di mergesort ha complessità O(nlogn) nel caso peggiore, e O(n) nel caso migliore, cioè quando l' array è già ordinato.

== Altri progetti ==