[prev] 6 [next]

Mergesort Performance

Best case: O(nlogn) comparisons
  • split array into equal-sized partitions
  • same happens at every recursive level
  • each "level" requires ≤ n comparisons, n moves
  • halving at each level ⇒ log2n levels
Worst case: O(nlogn) comparisons
  • partitions are exactly interleaved
  • need to compare all the way to end of partitions
Disadvantage over quicksort:   need extra storage O(n)

Advantage over quicksort:   best ≅ worst ≅ avg = O(nlogn)