Radix Sort
Counting-sort by each digit from least significant to most. Stability makes it work.
Counting and Radix Sort: Radix sort, ones then tens
in[6] = 25, ones digit 5. count[5] drops to 3, and that is its slot: out[3] = 25.
Cost
- Best
- O(d(n + b))
- Average
- O(d(n + b))
- Worst
- O(d(n + b))
- Space
- O(n + b)
d digits base b.
Properties
- No: Comparison based
- Yes: Stable
- No: In place
- No: Adaptive
- No: Online
Before this
Variants
- LSD Radix Sort
- MSD Radix Sort
Related
Leads to
Topics that need this one first.
Taught by the same lesson
Counting and Radix Sort covers these too, in the same run.