Skip to main content

Radix sort on 345, 654, 924, ...

Short answer

Radix sort uses LSD-first digit-by-digit stable sorting with 10 buckets. For the given numbers: after units pass: 911 72 123 654 924 345 555 56 57 808; after tens pass: 808 911 123 924 345 654 555 56 57 72; after hundreds pass (treating 2-digit numbers with 0 hundreds): 56, 57, 72, 123, 345, 555, 654, 808, 911, 924.

Explain Radix sort and sort the numbers 345, 654, 924, 123, 56, 72, 555, 808, 911 and 57.

Radix sort is a non-comparison sort that sorts integers digit by digit, starting from the least significant digit (LSD) to the most significant. For each digit position the numbers are distributed into 10 buckets (0 to 9) in the order they appear, then collected bucket by bucket from 0 to 9. The distribution must be stable, so the order from the earlier pass is kept within a bucket. For d-digit numbers, d passes are needed.

RadixSort(a, n, d)
for pass = 1 to d:                     (units, tens, hundreds, ...)
    put each number in bucket [digit of that pass]  (keep order)
    collect numbers from bucket 0 to bucket 9 into a

Data: 345, 654, 924, 123, 56, 72, 555, 808, 911, 57 (largest has 3 digits, so 3 passes)

Pass 1: units digit

Bucket0123456789
Numbers–91172123654, 924345, 5555657808–

After pass 1: 911, 72, 123, 654, 924, 345, 555, 56, 57, 808

Pass 2: tens digit

Bucket0123456789
Numbers808911123, 924–345654, 555, 56, 57–72––

After pass 2: 808, 911, 123, 924, 345, 654, 555, 56, 57, 72

Pass 3: hundreds digit (56, 57, 72 have hundreds digit 0)

Bucket0123456789
Numbers56, 57, 72123–345–555654–808911, 924

After pass 3: 56, 57, 72, 123, 345, 555, 654, 808, 911, 924

Complexity: O(d·(n + k)) for n numbers, d digits and base k = 10, so O(n) when d is fixed. It needs O(n + k) extra space and is stable.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Data Structure and Algorithm chapter 7 questions →