3.3.1 The Ω(n log n) lower bound for comparison sorting; comparing all sorts

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

Build-heap bottom-up costs? from Lesson 3.2.3
Quicksort worst case and when? from Lesson 3.2.2
Comparison-based search lower bound? from Lesson 2.1.2

1 · The Hook

🎣

Merge sort, heapsort and average quicksort all stop at n log n. Is that a coincidence, or a wall? It is a wall: any algorithm that sorts only by comparing elements needs Ω(n log n) comparisons in the worst case. The argument is the same decision tree you met for searching, with n! leaves instead of n.

2 · Predict First

🤔

Sorting 3 distinct elements a, b, c means finding which of the possible orders they are in. How many possible orders are there, and what is the least number of yes/no comparisons that can always tell them apart?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

3! = 6 orders. k comparisons distinguish at most 2ᵏ cases; 2² = 4 < 6 ≤ 8 = 2³, so 3 comparisons are needed in the worst case.

The decision-tree argument

Any comparison sort, on inputs of size n, can be drawn as a binary tree: each internal node is a comparison "aᵢ ≤ aⱼ?", each leaf an output order.
It must have a leaf for each of the n! possible orders.
A binary tree of height h has at most 2ʰ leaves, so 2ʰ ≥ n! → h ≥ log(n!) = Θ(n log n).
Worst-case comparisons of any comparison sort ≥ ⌈log₂ n!⌉: 3 for n = 3, 5 for n = 4, 7 for n = 5, 10 for n = 6, 16 for n = 8.
The same bound holds for the average case.

So merge sort and heapsort are asymptotically optimal comparison sorts. Beating n log n requires not comparing (Lesson 3.3.2).

Summary of comparison sorts

Sort	Best	Average	Worst	Extra space	Stable	In-place
Bubble (early exit)	n	n²	n²	O(1)	yes	yes
Selection	n²	n²	n²	O(1)	no	yes
Insertion	n	n²	n²	O(1)	yes	yes
Merge	n log n	n log n	n log n	O(n)	yes	no
Quick	n log n	n log n	n²	O(log n) stack	no	yes
Heap	n log n	n log n	n log n	O(1)	no	yes

Choosing in practice

Nearly sorted, or tiny arrays: insertion sort.
Guaranteed n log n with O(1) space: heapsort. Stable n log n: merge sort (also for linked lists and external sorting on disk).
Fastest on average in memory: quicksort with a random or median-of-three pivot.

4 · Visual

Decision tree for sorting a, b, c (6 leaves, height 3)

                     a<b?
              yes /        \ no
               b<c?          a<c?
             /     \        /     \
          a,b,c    a<c?   b,a,c    b<c?
                  /   \           /   \
               a,c,b c,a,b     b,c,a  c,b,a

5 · Worked Examples

Example 1 Easy

Minimum worst-case comparisons to sort 4 elements?

Solution

⌈log 24⌉ = 5.

Example 2 Medium

Which sorts in the table are both stable and Θ(n log n) worst case?

Solution

Only merge sort.

Example 3 GATE

A comparison-based algorithm sorts any 6 elements. What is the minimum number of comparisons it must make in the worst case?

Solution

⌈log 720⌉ = 10 (2⁹ = 512 < 720 ≤ 1024).

6 · GATE Traps

⚠️

The bound is for comparison sorts; counting/radix sort escape it.
log(n!) = Θ(n log n), not n² and not n.
Quicksort's worst case is n² even though it is "optimal on average".
Merge sort's extra space is Θ(n) on arrays.

7 · Memory Hook

🧠

"n! leaves need log n! levels."

8 · Connect the Dots

This lesson proved the comparison wall. Next: counting, radix and bucket sort, which go around it by looking at the keys' values instead of comparing them.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markLower bound

Minimum worst-case comparisons for any comparison sort on 5 elements?

Numerical answer: ________

Q2MCQ1 markOptimality

Which statement is correct?

(A) Quicksort is Θ(n log n) in the worst case.
(B) Insertion sort needs Ω(n log n) comparisons on sorted input.
(C) No sorting algorithm can run faster than Θ(n log n).
(D) Every comparison-based sort needs Ω(n log n) comparisons in the worst case.

Q3MSQ2 marksTable facts

Which are true?

(A) Quicksort's average case is Θ(n log n).
(B) Heapsort uses O(1) extra space.
(C) Selection sort's best case is Θ(n).
(D) Merge sort is stable.

Q4NAT2 marksLower bound n = 8

Minimum worst-case comparisons to sort 8 elements by comparisons?

Numerical answer: ________

Q5MCQ1 markChoice

Best choice for sorting an array that is already sorted except for a few swapped neighbours:

(A) Selection sort
(B) Insertion sort
(C) Heapsort
(D) Quicksort with first-element pivot

10 · Rule Card

Comparison sorting needs ≥ ⌈log n!⌉ = Ω(n log n) comparisons (worst and average).
Merge sort and heapsort are optimal; quicksort optimal on average.
Table: insertion for nearly sorted; heapsort for O(1) space; merge for stable; quicksort fastest on average.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

decision tree for sortingn! leavesΩ(n log n) lower bound⌈log n!⌉ minimum comparisonsasymptotically optimal sortcomparison-sort summary table

12 · Answer Vault

Answer Vault

Try the questions first. Open when you are ready to check.

Recall Warm-up

Θ(n).
Θ(n²), e.g. sorted input with an end pivot.
Ω(log n), from a decision tree with ≥ n leaves.