Radix Sort
Radix sort
Radix sort extends the bucket idea by separating an integer into digits. Prepare ten buckets for digits 0–9. Distribute by the units digit, gather by increasing bucket number while preserving arrival order within each bucket, and repeat for tens, hundreds, and higher positions.
For example:
Radix sort: distribute one digit, preserve arrival order
Unlock the complete interactive lab, deeper explanations, and curated reference answers.
Distribute by the units digit:
Gather the bucket contents into the array in order:
Distribute by the tens digit:
Gather the contents into the array again:
This example uses nonnegative decimal integers. Every pass must preserve arrival order within buckets. With d digits and radix b, time is and auxiliary space is .
KNOWLEDGE QUIZ
KNOWLEDGE QUIZ
Preserve order across two digit passes
Use decimal LSD radix sort on [42,7,23,12,31,2], padding missing high digits with zero. Draw units and tens buckets and each gathered array, preserving FIFO order.