Mergesort Performance
Best case: O(NlogN) comparisons
- split array into equal-sized partitions
- same happens at every recursive level
- each "level" requires ≤ N comparisons
- 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)
|
![[prev]](icon/prev.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}