Non-comparison sorts like counting / radix / bucket can run in O(n) because
Athey use a faster comparison instruction in modern CPUs
Bthe input is always already partially sorted
Cthey read bits or digits directly, bypassing the comparison-tree bound
Dthey break the comparison-based Ω(n log n) bound by using more memory
Answer & Solution
Correct answer: C. they read bits or digits directly, bypassing the comparison-tree bound
The Ω(n log n) bound applies only to algorithms that distinguish elements solely through comparisons. Counting / radix / bucket sorts look at the actual bit or digit representation of each element. That extra information lets them sort in O(n) when keys come from a bounded universe. It is not about a faster compare or input being pre-sorted.
Related questions
An NP-hard problem differs from an NP-complete one because NP-hard problemsThe first problem proved to be NP-complete wasA problem X is NP-complete if and only ifWhy does theoretical computer science draw the line at 'polynomial-time' for tractability?Which set inclusion is established (i.e., proven, not open)?The class NP is the set of decision problems for whichFloyd-Warshall detects the presence of a negative cycle byTopological sort is well-defined for