#sorting

Stanford CS161 Lecture 6：Sorting 下界與線性時間 Radix Sort

Ω(n log n) 只限制 comparison sorting。若整數 key 可直接索引 bucket，stable Counting Sort 可作為 Radix Sort 的內層；在 M≤n^c 等條件下能達 O(n)。