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

CountingSort, RadixSort

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.