AlgoScope

Radix Sort

Counting-sort by each digit from least significant to most. Stability makes it work.

Sorting, algorithm, intermediate
Place 25 at output index 3.0123456789incntout53891527184525000113456725

Counting and Radix Sort: Radix sort, ones then tens

Decision, step 10 of 33

in[6] = 25, ones digit 5. count[5] drops to 3, and that is its slot: out[3] = 25.

How counting and radix sort works

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 SortLeast significant digit first.
  • MSD Radix SortMost significant digit first

Leads to

Topics that need this one first.

Taught by the same lesson

Counting and Radix Sort covers these too, in the same run.