Algorithms and Data Structures · Middle · Question 7 of 75
Why can't any comparison sort beat O(n log n) in the worst case?
- 1Sorting always copies the whole array log n times
- ✓Correct answer: It must tell apart n! orderings: log(n!) ≈ n log n
- 3Every comparison takes O(log n) time in memory
Explanation
Each comparison has two outcomes, so k comparisons distinguish at most 2ᵏ orderings. To identify one of n! orderings you need log₂(n!) comparisons, which is Θ(n log n).