Radix Sort Algorithm in DSA Java

Mental Model

Radix sort sorts numbers by processing digits from least to most significant, grouping numbers by each digit step by step.

Analogy: Imagine sorting mail by zip code: first by the last digit, then the second last, and so on, until fully sorted.

Unsorted array:
[170, 45, 75, 90, 802, 24, 2, 66]
Buckets for digit 0-9:
0: []
1: []
2: []
3: []
4: []
5: []
6: []
7: []
8: []
9: []

Dry Run Walkthrough

Input: list: [170, 45, 75, 90, 802, 24, 2, 66]

Goal: Sort the list in ascending order using radix sort by processing digits from least significant to most significant.

Step 1: Sort by least significant digit (units place)

Buckets:
0: [170, 90]
2: [802, 2]
4: [24]
5: [45, 75]
6: [66]
Others: []
Array after collecting buckets:
170 -> 90 -> 802 -> 2 -> 24 -> 45 -> 75 -> 66 -> null

Why: Group numbers by their units digit to partially sort by the smallest place value.

Step 2: Sort by second least significant digit (tens place)

Buckets:
0: [802, 2]
2: [24]
4: [45]
6: [66]
7: [170, 75]
9: [90]
Others: []
Array after collecting buckets:
802 -> 2 -> 24 -> 45 -> 66 -> 170 -> 75 -> 90 -> null

Why: Group numbers by their tens digit to refine sorting order.

Step 3: Sort by most significant digit (hundreds place)

Buckets:
0: [2, 24, 45, 66, 75, 90]
1: [170]
8: [802]
Others: []
Array after collecting buckets:
2 -> 24 -> 45 -> 66 -> 75 -> 90 -> 170 -> 802 -> null

Why: Group numbers by their hundreds digit to finalize sorting order.

Result:

2 -> 24 -> 45 -> 66 -> 75 -> 90 -> 170 -> 802 -> null

Annotated Code

DSA Java

import java.util.*;

public class RadixSort {

    // Function to get the digit at exp place
    static int getDigit(int num, int exp) {
        return (num / exp) % 10;
    }

    // Radix sort function
    static void radixSort(int[] arr) {
        int max = Arrays.stream(arr).max().orElse(0);

        // Start with least significant digit
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countingSortByDigit(arr, exp);
        }
    }

    // Counting sort based on digit at exp
    static void countingSortByDigit(int[] arr, int exp) {
        int n = arr.length;
        int[] output = new int[n];
        int[] count = new int[10];

        // Count occurrences of digits
        for (int i = 0; i < n; i++) {
            int digit = getDigit(arr[i], exp);
            count[digit]++;
        }

        // Change count[i] so it contains actual position
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }

        // Build output array from right to left to keep stability
        for (int i = n - 1; i >= 0; i--) {
            int digit = getDigit(arr[i], exp);
            output[count[digit] - 1] = arr[i];
            count[digit]--;
        }

        // Copy output to arr
        for (int i = 0; i < n; i++) {
            arr[i] = output[i];
        }
    }

    // Driver code
    public static void main(String[] args) {
        int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
        radixSort(arr);
        for (int num : arr) {
            System.out.print(num + " -> ");
        }
        System.out.print("null\n");
    }
}

for (int exp = 1; max / exp > 0; exp *= 10) {

iterate over digit places from least significant to most significant

int digit = getDigit(arr[i], exp);

extract digit at current place value for counting

count[digit]++;

count frequency of each digit

count[i] += count[i - 1];

accumulate counts to get positions

output[count[digit] - 1] = arr[i];

place element in output array maintaining stability

arr[i] = output[i];

copy sorted output back to original array

Output

2 -> 24 -> 45 -> 66 -> 75 -> 90 -> 170 -> 802 -> null

Complexity Analysis

Time: O(d * (n + k)) where d is number of digits, n is number of elements, k=10 for digits; because we do counting sort for each digit place.

Space: O(n + k) for output and count arrays used in counting sort.

vs Alternative: Compared to comparison sorts like quicksort O(n log n), radix sort can be faster for fixed digit sizes because it sorts in linear time relative to input size.

Edge Cases

Empty array

No sorting needed, function handles gracefully without error.

DSA Java

int max = Arrays.stream(arr).max().orElse(0);

Array with one element

Returns the same single element array without changes.

DSA Java

for (int exp = 1; max / exp > 0; exp *= 10) {

Array with all elements the same

Sorting steps run but array remains unchanged.

DSA Java

count[digit]++;

When to Use This Pattern

When you need to sort integers or fixed-length strings efficiently without comparisons, reach for radix sort because it sorts by processing digits stepwise.

Common Mistakes

Mistake: Not maintaining stability during counting sort step, causing incorrect final order.
Fix: Build output array from right to left to keep relative order of equal digits.

Mistake: Stopping after sorting by least significant digit only.
Fix: Iterate over all digit places until the most significant digit is processed.

Summary

Radix sort sorts numbers digit by digit from least to most significant.

Use it to sort integers efficiently when digit length is fixed or small.

The key insight is grouping numbers by each digit stepwise to achieve full sorting.

Practice

1. What is the main idea behind the Radix Sort algorithm?

easy

A. Sort numbers digit by digit starting from the least significant digit

B. Compare each element with every other element and swap if needed

C. Divide the array into halves and sort each half recursively

D. Use a pivot element to partition the array and sort partitions

Solution

1. Step 1: Understand Radix Sort approach

   Radix Sort sorts numbers by processing individual digits starting from the least significant digit (rightmost) to the most significant digit (leftmost).

2. Step 2: Compare with other sorting methods

   Other options describe Bubble Sort, Merge Sort, and Quick Sort, which are different algorithms.

3. Final Answer:

   Sort numbers digit by digit starting from the least significant digit -> Option A

4. Quick Check:

   Radix Sort = Digit by digit sorting [OK]

Hint: Radix Sort processes digits from right to left [OK]

Common Mistakes:

• Confusing Radix Sort with comparison-based sorts
• Thinking it sorts from most significant digit first
• Assuming it uses pivot or divide and conquer

2. Which of the following is the correct way to get the digit at position pos (starting from 0 for least significant digit) of a number num in Java?

easy

A. (num % (int) Math.pow(10, pos)) / 10

B. (num / (int) Math.pow(10, pos)) % 10

C. (num * (int) Math.pow(10, pos)) % 10

D. (num % 10) / (int) Math.pow(10, pos)

Solution

1. Step 1: Understand digit extraction logic

   To get the digit at position pos, divide num by 10^pos to shift digits right, then take modulo 10 to get the last digit.

2. Step 2: Check each option

   (num / (int) Math.pow(10, pos)) % 10 correctly divides num by 10^pos and then modulo 10. Others do incorrect operations.

3. Final Answer:

   (num / (int) Math.pow(10, pos)) % 10 -> Option B

4. Quick Check:

   Digit extraction = divide then modulo [OK]

Hint: Divide by 10^pos then mod 10 to get digit [OK]

Common Mistakes:

• Using modulo before division
• Multiplying instead of dividing
• Incorrect order of operations

3. What will be the output array after one pass of Radix Sort on the array [170, 45, 75, 90, 802] sorting by the least significant digit (units place)?

medium

A. [45, 75, 90, 170, 802]

B. [802, 170, 90, 45, 75]

C. [170, 90, 802, 45, 75]

D. [75, 45, 170, 90, 802]

Solution

1. Step 1: Extract least significant digit of each number

   170 -> 0, 45 -> 5, 75 -> 5, 90 -> 0, 802 -> 2

2. Step 2: Sort array by these digits

   Order by digits: 0s first (170, 90), then 2 (802), then 5s (45, 75). So array becomes [170, 90, 802, 45, 75]

3. Final Answer:

   [170, 90, 802, 45, 75] -> Option C

4. Quick Check:

   Sort by units digit = [170, 90, 802, 45, 75] [OK]

Hint: Sort by digit at current place only [OK]

Common Mistakes:

• Sorting entire numbers instead of digits
• Mixing digit positions
• Ignoring stable sorting requirement

4. Consider this Java code snippet for Radix Sort digit extraction:

int digit = (num % (int) Math.pow(10, pos)) / (int) Math.pow(10, pos - 1);

What is the error in this code?

medium

A. No error, code works correctly

B. Incorrect order of modulo and division operations

C. Casting to int causes loss of precision

D. Division by zero when pos = 0

Solution

1. Step 1: Analyze division when pos = 0

   When pos = 0, expression divides by Math.pow(10, -1), which is 10^-1 = 0.1, but casting to int makes it 0, causing division by zero error.

2. Step 2: Check other options

   Modulo and division order is correct for digit extraction, casting is intentional, so no other errors.

3. Final Answer:

   Division by zero when pos = 0 -> Option D

4. Quick Check:

   pos=0 causes division by zero [OK]

Hint: Check division by zero for edge digit positions [OK]

Common Mistakes:

• Ignoring pos=0 edge case
• Assuming casting fixes division issues
• Thinking modulo order is wrong

5. Given the array [329, 457, 657, 839, 436, 720, 355], how many passes (iterations over digits) will Radix Sort perform to fully sort this array?

hard

A. 3 passes

B. 4 passes

C. 2 passes

D. 1 pass

Solution

1. Step 1: Find the maximum number of digits in the array

   The largest number is 839, which has 3 digits.

2. Step 2: Determine passes needed

   Radix Sort performs one pass per digit, so 3 passes are needed (units, tens, hundreds).

3. Final Answer:

   3 passes -> Option A

4. Quick Check:

   Max digits = 3, passes = 3 [OK]

Hint: Passes = number of digits in largest number [OK]

Common Mistakes:

• Counting array length instead of digit count
• Assuming fixed number of passes
• Ignoring leading zeros in numbers