← 🔀 Sorting & Searching
Subtopic 5 of 6

2.5Lower bound and comparison summary

The idea

Any comparison-based sort needs at least about n log n comparisons in the worst case. A summary table of all sorts is worth memorising.

Think of it like this: Twenty questions: with n! possible orderings you need at least log₂(n!) yes/no answers.

Why it exists

GATE asks which sort is stable, in place, or best on nearly sorted data.

How it works

  1. A decision tree has n! leaves.
  2. A binary tree with n! leaves has height ≥ log₂(n!) = Θ(n log n).
  3. So no comparison sort can beat n log n in the worst case.
  4. Use the table to pick: nearly sorted → insertion; guaranteed n log n → merge or heap.

Worked example: Which sort is best for an almost sorted array?

Insertion sort: it costs n − 1 plus the number of inversions, so nearly sorted data is close to linear.

Now play with it

  • →Compare the best and worst columns of the table.
  • →Spot the only two with O(1) extra space and Θ(n log n) worst case.
SortBestAverageWorstExtra spaceStable?
Bubble (early exit)O(n)O(n²)O(n²)O(1)yes
InsertionO(n)O(n²)O(n²)O(1)yes
SelectionO(n²)O(n²)O(n²)O(1)no
MergeO(n log n)O(n log n)O(n log n)O(n)yes
Quick (last pivot)O(n log n)O(n log n)O(n²)O(log n) stackno
HeapO(n log n)O(n log n)O(n log n)O(1)no

Any comparison sort needs Ω(n log n) in the worst case: a decision tree with n! leaves has height ⌈log₂ n!⌉.

Check yourself

The minimum number of comparisons needed in the worst case to sort 4 elements is at least

Remember: Comparison sorts: Ω(n log n) from n! leaves.
Exam notes (the dense version)

Any comparison sort needs Ω(n log n) comparisons in the worst case, because a decision tree with n! leaves has height ≥ log₂(n!) = Θ(n log n). Know the table: best, average, worst, extra space and stability of every sort. Sorting is also the engine behind many problems (duplicates, closest pair, interval merging).

Previous year questions: Sorting & Searching (9)

PYQs are grouped by topic, so this is the full set for Sorting & Searching; try the ones that match this subtopic. Open all 9 on the topic page.