Sorting Lower Bounds and Linear-Time Radix Sort | Stanford CS161 Lecture 6
The Ω(n log n) lower bound applies to comparison sorting. When integer keys can index buckets directly, stable Counting Sort can power Radix Sort and achieve O(n) under conditions such as M≤n^c.