[prev] 48 [next]

Quicksort Performance

Best case: O(nlogn) comparisons
  • choice of pivot gives two equal-sized partitions
  • same happens at every recursive level
  • each "level" requires approx n comparisons
  • halving at each level ⇒ log2n levels
Worst case: O(n2) comparisons
  • always choose lowest/highest value for pivot
  • partitions are size 1 and n-1
  • each "level" requires approx n comparisons
  • partitioning to 1 and n-1 ⇒ n levels