Stanford CS161 Lecture 6: Sorting Lower Bounds and Linear-Time Radix Sort
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.