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

# Radix sort definition and algorithm

Data Structure and Algorithm · Chapter 7: Sorting

- Asked in: 2072 Asoj, 5 marks
- Video: [L-3.9: Radix Sort | Easiest explanation with example](https://www.youtube.com/watch?v=9QSgBO9yjKU) — Gate Smashers
- 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-algorithm
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-7

## Question

Define a radix sort with its algorithm.

## Short answer

Radix sort is a non-comparison sort that sorts integers digit by digit, LSD first. It distributes numbers into 10 queues based on the current digit, then collects them in queue order. Repeating for all digits yields a sorted list. Time complexity O(d·n), extra space O(n), stable.

## Answer

Radix sort is a non-comparison sorting method that sorts keys digit by digit, starting from the least significant digit (LSD) and moving to the most significant digit. For each digit position the keys are distributed into 10 queues (pockets), numbered 0 to 9, and then collected back in queue order. Because each pass is stable, after the last pass the list is sorted.

#### Algorithm
1. Find the largest key and count its digits, *d*.
2. For pass = 1 to *d* (units, tens, hundreds, ...):
   1. Take each key from the list in order and insert it at the rear of queue[digit], where digit is the current digit of the key.
   2. Delete all keys from queue 0, then queue 1, ... up to queue 9 (front to rear) and place them back in the list.
3. After *d* passes the list is sorted.

```c
void radixSort(int a[], int n) {
    int max = a[0], exp, i, j, k;
    for (i = 1; i < n; i++) if (a[i] > max) max = a[i];
    for (exp = 1; max / exp > 0; exp *= 10) {
        int q[10][100], cnt[10] = {0};          /* 10 queues */
        for (i = 0; i < n; i++) {               /* distribute */
            int d = (a[i] / exp) % 10;
            q[d][cnt[d]++] = a[i];
        }
        k = 0;
        for (j = 0; j < 10; j++)                /* collect */
            for (i = 0; i < cnt[j]; i++) a[k++] = q[j][i];
    }
}
```

**Complexity:** each pass takes O(n) and there are *d* passes, so time is O(d·n) (O(n) when *d* is fixed). Extra space is O(n) for the queues. It is stable and needs no key comparisons.

## Check yourself

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

1. What kind of sort is radix sort?
   A. Comparison-based divide and conquer
   B. Non-comparison sort that works digit by digit
   C. A selection sort
   D. Exchange sort
   Answer: B. It never compares whole keys; it distributes by digits. (Key point: Non-comparison)

2. How many passes does radix sort make?
   A. n
   B. The number of digits d of the largest key
   C. log n
   D. 10
   Answer: B. One pass per digit position. (Key point: Passes)

3. After distributing, how are keys collected?
   A. From queue 9 to queue 0
   B. From queue 0 to queue 9, front to rear
   C. Randomly
   D. Only from the non-empty largest queue
   Answer: B. Collecting in queue order 0 to 9 keeps the sort correct. (Key point: Collect step)

4. What are time and space for radix sort?
   A. O(d*n) time, O(n) extra space, stable
   B. O(n^2) time, in-place
   C. O(n log n) time, unstable
   D. O(d) time, O(1) space
   Answer: A. Each pass is O(n), with d passes; queues need extra space. (Key point: Complexity)

## Related in Data Structure and Algorithm

- [Radix sort on 345, 654, 924, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aradix-sort-345-654) — 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 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
- [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
- [Algorithm for an exchange sort](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aexchange-sort-algorithm) — Data Structure and Algorithm, chapter 7, asked 2×
- [Merge sort algorithm and trace](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Amerge-sort-algorithm-trace) — Data Structure and Algorithm, chapter 7