Algorithms and Data Structures · Middle · Question 8 of 75
When can counting sort beat O(n log n)?
- 1When the array is already almost fully sorted
- 2When elements are strings of the same length
- ✓Correct answer: For small integer keys in range k: O(n + k)
Explanation
Counting sort doesn't compare elements: it counts how many times each key occurs and writes them back in order. It's great for ages or grades, but a huge range of keys makes the count array too large.