Merge-sort (5)
Analysis (continued):
Therefore: comps(n) ? 2 comps(n/2) + n – 1 if n > 1 comps(n) = 0 if n ? 1
Solution: comps(n) ? n log2n
Time complexity is O(n log n).
Space complexity is O(n), since step 1.4 needs an auxiliary array of length n.
Diapositive précédente
Diapositive suivante
Revenir à la première diapositive
Afficher la version graphique