MEPX
Chapter 5 of 12All chapters
  1. 1Why complexity matters
  2. 2Reading Big O
  3. 3Constant and linear time
  4. 4Logarithmic time
  5. 5Sorting and its floor
  6. 6Quadratic and worse
  7. 7Best, average and worst
  8. 8Space complexity
  9. 9Amortised analysis
  10. 10Costs by data structure
  11. 11Recursion and recurrences
  12. 12Choosing an algorithm

Chapter 5 of 12

Sorting and its floor

Why O(n log n) is the wall.

The lower bound

Any algorithm that sorts by comparing pairs needs at least O(n log n) comparisons in the worst case. Merge sort and heap sort meet that bound every time.

  • Quicksort averages O(n log n) but degrades to O(n squared) when the pivot splits badly.
  • Most standard libraries use a hybrid such as Timsort, tuned for partly sorted input.

Beating the bound

Counting sort and radix sort run in linear time because they never compare two values. They need extra assumptions, such as small integer keys, so they are specialist tools.