Radix Sort Algorithm in DSA Java - Time & Space Complexity

Time Complexity: Radix Sort Algorithm

O(d * (n + k))

Understanding Time Complexity

We want to understand how the time taken by Radix Sort changes as the list size grows.

Specifically, how the number of steps grows when sorting more numbers.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public void radixSort(int[] arr) {
    int max = Arrays.stream(arr).max().getAsInt();
    for (int exp = 1; max / exp > 0; exp *= 10) {
        countingSortByDigit(arr, exp);
    }
}

private void countingSortByDigit(int[] arr, int exp) {
    int n = arr.length;
    int[] output = new int[n];
    int[] count = new int[10];
    for (int i = 0; i < n; i++) {
        count[(arr[i] / exp) % 10]++;
    }
    for (int i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }
    for (int i = n - 1; i >= 0; i--) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }
    System.arraycopy(output, 0, arr, 0, n);
}
    

This code sorts numbers by processing each digit from least to most significant using counting sort.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The outer loop runs once per digit place (like ones, tens, hundreds).
• How many times: The counting sort inside runs for every digit, processing all elements each time.

How Execution Grows With Input

As the number of elements grows, the algorithm processes each element for every digit in the largest number.

Input Size (n)	Approx. Operations
10	About 20 to 30 steps (depends on digit count)
100	About 200 to 300 steps
1000	About 2000 to 3000 steps

Pattern observation: Operations grow roughly in direct proportion to the number of elements and the number of digits.

Final Time Complexity

Time Complexity: O(d * (n + k))

This means the time grows with the number of elements (n), the number of digits (d), and the digit range (k, here 10).

Common Mistake

[X] Wrong: "Radix Sort is always faster than comparison sorts like QuickSort."

[OK] Correct: Radix Sort depends on digit count and range; for large digit counts or small arrays, comparison sorts can be faster.

Interview Connect

Understanding Radix Sort's time complexity helps you explain when and why to use it, showing clear thinking about algorithm choices.

Self-Check

"What if the numbers had more digits or a larger digit range? How would that affect the time complexity?"

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