GATE CS 1991 Q01 — Searching, Sorting, Hashing

To find the minimum number of comparisons required to sort $n$ elements in the worst case, we use the information-theoretic lower bound for comparison-based sorting.

Any comparison-based sorting algorithm can be represented as a binary decision tree. A binary tree of height $h$ has at most $2^h$ leaves. Since there are $n!$ possible permutations of $n$ elements, the decision tree must have at least $n!$ leaves to correctly sort all possible inputs.

Therefore, the minimum height $h$ (which represents the minimum number of comparisons in the worst case) must satisfy:

For $n = 5$ elements:

Since $2^6 = 64$ and $2^7 = 128$:

Thus, at least $7$ comparisons are theoretically required. This lower bound is tight, as the Ford-Johnson algorithm (merge-insertion sort) can sort $5$ elements using exactly $7$ comparisons in the worst case.