A strong answer
The O(n log n) bound applies to comparison sorts, which learn about the input only by comparing pairs. There are n! possible orderings, and each comparison has two outcomes, so distinguishing them all needs at least log₂(n!) comparisons, about n log₂ n − 1.44n. Merge sort and heap sort meet that bound up to a constant.
Sorts that use the keys' values instead of comparisons aren't bound by it. Counting sort handles integers in a small range 0 to k: count each value, turn counts into starting positions with a prefix sum, then place each element. It is O(n + k) and stable. Radix sort handles fixed-width keys by applying a stable counting sort to one digit at a time, least significant first; 32-bit integers take 4 passes of 256 buckets, so O(d(n + b)), linear in n. Bucket sort spreads values that are roughly uniformly distributed across n buckets and sorts each small bucket, for expected O(n).
The limits: counting sort needs k to be small relative to n; radix sort needs keys that decompose into digits, extra tricks for negatives and floats (flip the sign bit, and all bits for negative floats), and O(n) extra memory; and their scattered writes are hard on the cache, so for small or medium arrays a good comparison sort is often faster. They shine on large arrays of integers, for example in GPU sorting libraries and analytics engines.
What the interviewer is listening for
- The lower bound and exactly what it assumes.
- Counting sort and radix sort, including why radix passes must be stable.
- Honest limits: key type, range, memory and cache behavior.
Common mistakes
- Saying radix sort beats every sort; it depends on key size and the data.
- Forgetting that counting sort's cost includes the range k.
- Using an unstable sort for radix passes.