---
title: "Radix sort on 345, 654, 924, ..."
subject: "Data Structure and Algorithm"
chapter: 7
key: "semester_4/data_structure_and_algorithm:radix-sort-345-654"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/radix-sort-345-654
site: BCT Engineering
---

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

Data Structure and Algorithm · Chapter 7: Sorting

- Asked in: 2073 Magh, 8 marks
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/radix-sort-345-654
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-7

## Question

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

## 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.

## Answer

**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.

```text
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**
| Bucket | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| Numbers | – | 911 | 72 | 123 | 654, 924 | 345, 555 | 56 | 57 | 808 | – |

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

**Pass 2: tens digit**
| Bucket | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| Numbers | 808 | 911 | 123, 924 | – | 345 | 654, 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)
| Bucket | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| Numbers | 56, 57, 72 | 123 | – | 345 | – | 555 | 654 | – | 808 | 911, 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.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. Which digit does LSD radix sort process first?
   A. Most significant digit
   B. Least significant digit
   C. Middle digit
   D. The largest digit
   Answer: B. LSD radix sort starts from the units digit. (Key point: Digit order)

2. How many passes are needed for 345, 654, 924, 123, 56, 72, 555, 808, 911, 57?
   A. 2
   B. 3
   C. 10
   D. 4
   Answer: B. The largest has 3 digits, so 3 passes. (Key point: Number of passes)

3. Why must distribution within a bucket be stable?
   A. To use fewer buckets
   B. So order from earlier passes is preserved among equal digits
   C. To avoid comparisons
   D. To sort descending
   Answer: B. Otherwise the work of earlier passes would be lost. (Key point: Stability)

4. What is the sorted result?
   A. 56, 57, 72, 123, 345, 555, 654, 808, 911, 924
   B. 123, 345, 555, 56, 57, 72, 654, 808, 911, 924
   C. 924, 911, 808, 654, 555, 345, 123, 72, 57, 56
   D. 56, 72, 57, 123, 345, 555, 654, 808, 911, 924
   Answer: A. Ascending order after the hundreds pass. (Key point: Final result)

## Related in Data Structure and Algorithm

- [Radix sort on 25, 57, 48, 37, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aradix-sort-25-57-48) — Data Structure and Algorithm, chapter 7
- [Merge and radix sort on 142, 523, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Amerge-radix-trace-142) — Data Structure and Algorithm, chapter 7
- [Radix sort definition and algorithm](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aradix-sort-algorithm) — Data Structure and Algorithm, chapter 7
- [Radix sort on 32, 45, 60, 83, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aradix-sort-32-45-60) — Data Structure and Algorithm, chapter 7
- [Merge sort on 47, 27, 56, 23, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Amerge-sort-trace-47-27) — Data Structure and Algorithm, chapter 7

## Related in other subjects

- [Disk scheduling, 1000 cylinders, head at 345](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Adisk-1000-cyl-fifo-sstf-scan) — Operating System, chapter 6
- [Chi-square uniformity test, 40 numbers](https://www.bctengineer.com/question.md?key=semester_8%2Fsimulation_and_modeling%3Achi-square-uniformity-table-2074) — Simulation and Modeling, chapter 6