Sorting lower bounds and O(n)-time sorting
two (more) models
一. Comparison-based sorting model
MergeSort, QuickSort, InsertionSort
must take at least nlogn steps
Each internal node has two children, one for “yes” and one for “no.”
Running an algorithm on a particular input corresponds to a particular path through the tree.
二. Another model
Can run in O(n) time
RadixSort：Can use less space than CountingSort
RadixSort CountingSort on the least-significant digit first, then the next least-significant, and so on.