Radix Sort Algorithm in DSA Java - Deep Dive

Overview - Radix Sort Algorithm

What is it?

Radix Sort is a way to sort numbers by looking at their digits one by one, starting from the smallest place value (like ones) to the largest (like thousands). It groups numbers based on each digit and rearranges them until all digits are processed. This method does not compare numbers directly but sorts them by their parts. It works best when sorting numbers with the same number of digits or strings of equal length.

Why it matters

Without Radix Sort, sorting large lists of numbers might take longer because comparing each number directly can be slow. Radix Sort speeds up sorting by breaking numbers into smaller pieces and sorting those pieces quickly. This helps in applications like organizing phone numbers, IDs, or large datasets where fast sorting is important. Without it, some tasks would be slower and less efficient.

Where it fits

Before learning Radix Sort, you should understand basic sorting methods like Bubble Sort and Counting Sort. After Radix Sort, you can explore more advanced sorting algorithms like Quick Sort and Merge Sort, and learn about algorithm efficiency and complexity.

Mental Model

Core Idea

Radix Sort sorts numbers by processing each digit from the smallest place to the largest, grouping and rearranging them step-by-step without direct comparisons.

Think of it like...

Imagine sorting mail by zip code digits: first by the last digit, then the second last, and so on, until all mail is perfectly ordered.

Step 1: Sort by least significant digit (ones place)
┌───────────────┐
│ 170, 45, 75   │
│ Sorted by 0:  │
│ 170, 45, 75   │
└───────────────┘
Step 2: Sort by next digit (tens place)
┌───────────────┐
│ 170, 45, 75   │
│ Sorted by 7:  │
│ 45, 170, 75   │
└───────────────┘
Step 3: Sort by next digit (hundreds place)
┌───────────────┐
│ 45, 170, 75   │
│ Sorted by 1:  │
│ 45, 75, 170   │
└───────────────┘

Build-Up - 7 Steps

1

Foundation

Understanding Digit-by-Digit Sorting

Concept: Radix Sort processes numbers one digit at a time, starting from the smallest digit.

Imagine you have numbers like 170, 45, and 75. Instead of comparing whole numbers, Radix Sort looks at the last digit first (ones place). It groups numbers by this digit, then moves to the next digit (tens place), and so on until all digits are sorted.

Result

Numbers are grouped and partially sorted by each digit, preparing for the next step.

Understanding that sorting can happen digit by digit helps break down complex sorting into simple, repeatable steps.

2

Foundation

Using Counting Sort as a Subroutine

Concept: Radix Sort uses Counting Sort to sort numbers based on each digit efficiently.

Counting Sort counts how many times each digit appears and uses this to place numbers in the correct order for that digit. It is stable, meaning numbers with the same digit keep their original order, which is important for Radix Sort to work correctly.

Result

Each digit-based sort rearranges numbers without losing previous order, ensuring correct final sorting.

Knowing that Counting Sort is stable and efficient for digits is key to Radix Sort's success.

3

Intermediate

Handling Numbers with Different Digit Lengths

🤔Before reading on: Do you think Radix Sort can sort numbers with different digit lengths without extra steps? Commit to yes or no.

Concept: Radix Sort handles numbers with different lengths by treating missing digits as zero or padding numbers.

For example, sorting 7 and 170, Radix Sort treats 7 as 007 to match digit places. This ensures all numbers have the same number of digits during sorting steps.

Result

Numbers with different lengths are sorted correctly by equalizing digit places.

Understanding digit padding prevents errors and ensures Radix Sort works on varied inputs.

4

Intermediate

Stability Importance in Radix Sort

🤔Before reading on: Is it okay if the sorting of digits changes the order of numbers with the same digit? Commit to yes or no.

Concept: Radix Sort requires stable sorting at each digit step to maintain the order of numbers with the same digit.

If sorting by the tens digit changes the order of numbers with the same tens digit, the final result will be wrong. Stability means numbers with equal digits keep their relative order from previous steps.

Result

Stable sorting preserves partial order, leading to correct final sorting.

Knowing why stability matters helps avoid common mistakes and ensures Radix Sort's correctness.

5

Intermediate

Time Complexity and When Radix Sort Excels

🤔Before reading on: Do you think Radix Sort is always faster than comparison-based sorts like Quick Sort? Commit to yes or no.

Concept: Radix Sort runs in linear time relative to the number of digits and items, making it faster for large datasets with small digit ranges.

Radix Sort's time depends on the number of digits (d) and number of items (n), roughly O(d*(n+k)) where k is digit range (usually 10). For fixed digit sizes, this is close to O(n), faster than O(n log n) comparison sorts.

Result

Radix Sort is efficient for sorting large lists of numbers with limited digit size.

Understanding time complexity helps choose Radix Sort when it truly benefits performance.

6

Advanced

Implementing Radix Sort in Java

🤔Before reading on: Can you predict how Counting Sort integrates inside Radix Sort code? Commit to your answer.

Concept: Radix Sort implementation uses Counting Sort repeatedly for each digit place, updating the array step-by-step.

Java code example: public class RadixSort { static void countingSort(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--) { int digit = (arr[i] / exp) % 10; output[count[digit] - 1] = arr[i]; count[digit]--; } for (int i = 0; i < n; i++) arr[i] = output[i]; } static void radixSort(int[] arr) { int max = arr[0]; for (int num : arr) if (num > max) max = num; for (int exp = 1; max / exp > 0; exp *= 10) countingSort(arr, exp); } 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 + " "); } }

Result

Sorted output: 2 24 45 66 75 90 170 802

Seeing the full code clarifies how digit-wise sorting and stability combine in practice.

7

Expert

Radix Sort Limitations and Optimizations

🤔Before reading on: Do you think Radix Sort works well for floating-point numbers or strings without changes? Commit to yes or no.

Concept: Radix Sort needs adaptations for non-integer data and can be optimized by choosing base and handling memory carefully.

Radix Sort is mainly for integers. For floating points, you must handle sign and decimal parts carefully. For strings, fixed length or padding is needed. Choosing a larger base (like 256) can reduce passes but increase memory. Also, in-place versions exist but are complex.

Result

Understanding these limits helps apply Radix Sort correctly and efficiently in real systems.

Knowing Radix Sort's boundaries and tweaks prevents misuse and unlocks advanced performance gains.

Under the Hood

Radix Sort works by repeatedly grouping numbers based on individual digits, starting from the least significant digit. It uses a stable sorting method (like Counting Sort) to reorder numbers without disturbing previous digit order. Internally, it counts occurrences of each digit, calculates positions, and rearranges numbers in a temporary array before copying back. This process repeats for each digit place until the entire number is sorted.

Why designed this way?

Radix Sort was designed to avoid direct comparisons between whole numbers, which can be costly. By breaking numbers into digits and sorting those digits, it leverages the limited range of digits (0-9) for efficiency. Stability is crucial to preserve order across digit passes. Alternatives like comparison sorts have higher time complexity, so Radix Sort offers a faster option for fixed-length keys.

Input Array
┌───────────────┐
│ 170, 45, 75  │
└──────┬────────┘
       │ Sort by ones digit
       ▼
┌───────────────┐
│ 170, 45, 75  │
└──────┬────────┘
       │ Sort by tens digit
       ▼
┌───────────────┐
│ 45, 170, 75  │
└──────┬────────┘
       │ Sort by hundreds digit
       ▼
┌───────────────┐
│ 45, 75, 170  │
└───────────────┘

Myth Busters - 4 Common Misconceptions

Quick: Does Radix Sort compare whole numbers directly during sorting? Commit to yes or no.

Common Belief: Radix Sort compares whole numbers directly like other sorting algorithms.

Reality: Radix Sort never compares whole numbers directly; it sorts numbers digit by digit using a stable sub-sort.

Why it matters: Believing it compares whole numbers leads to misunderstanding its efficiency and when to use it.

Quick: Can Radix Sort handle negative numbers without changes? Commit to yes or no.

Common Belief: Radix Sort can sort negative numbers just like positive ones without any modification.

Reality: Radix Sort requires special handling for negative numbers, such as separating negatives and positives or using offsetting.

Why it matters: Ignoring this causes incorrect sorting results or runtime errors in real applications.

Quick: Is Radix Sort always faster than Quick Sort regardless of input? Commit to yes or no.

Common Belief: Radix Sort is always faster than comparison-based sorts like Quick Sort.

Reality: Radix Sort is faster only when the number of digits is small and fixed; otherwise, Quick Sort can be faster.

Why it matters: Misusing Radix Sort on large digit ranges can lead to worse performance.

Quick: Does Radix Sort work well for sorting strings of varying lengths without padding? Commit to yes or no.

Common Belief: Radix Sort can sort strings of different lengths without any adjustments.

Reality: Radix Sort requires strings to be of equal length or padded to work correctly.

Why it matters: Failing to pad strings leads to incorrect order and bugs.

Expert Zone

1

Choosing the base (radix) affects performance: higher base reduces passes but increases memory and complexity.

2

Stable sorting at each digit is non-negotiable; even a small instability breaks the entire sort.

3

In-place Radix Sort variants exist but are complex and rarely used in practice due to overhead.

When NOT to use

Radix Sort is not suitable for data with very large or variable digit lengths, floating-point numbers without adaptation, or when memory is limited. In such cases, comparison-based sorts like Quick Sort or Merge Sort are better choices.

Production Patterns

Radix Sort is used in systems sorting fixed-length keys like IP addresses, phone numbers, or large integer datasets. It is also used in distributed systems where digit-based partitioning helps parallelize sorting.

Connections

Counting Sort

Radix Sort builds on Counting Sort as a stable subroutine for sorting digits.

Understanding Counting Sort's stability and efficiency is essential to grasp how Radix Sort achieves its performance.

Bucket Sort

Both Radix Sort and Bucket Sort distribute elements into groups based on parts of their value.

Knowing Bucket Sort helps understand Radix Sort's grouping and distribution approach.

Human Sorting of Postal Mail

Radix Sort mimics the real-world process of sorting mail by zip code digits from right to left.

Recognizing this connection shows how algorithms often reflect practical human problem-solving methods.

Common Pitfalls

#1 Ignoring stability in the digit sorting step.

Wrong approach:

Using a non-stable sort like selection sort for each digit pass, which rearranges equal digits arbitrarily.

Correct approach:

Using Counting Sort or another stable sort to maintain order of equal digits during each pass.

Root cause:

Misunderstanding that stability is required to preserve previous digit order and ensure correct final sorting.

#2 Not handling numbers with different digit lengths properly.

Wrong approach:

Sorting numbers like 7 and 170 directly without padding or treating missing digits as zero.

Correct approach:

Padding shorter numbers with leading zeros or treating missing digits as zero during sorting.

Root cause:

Assuming all numbers have the same number of digits, leading to incorrect grouping and sorting.

#3 Applying Radix Sort to negative numbers without adjustments.

Wrong approach:

Running Radix Sort directly on negative and positive numbers mixed together.

Correct approach:

Separating negative and positive numbers, sorting them separately, then combining results or offsetting values.

Root cause:

Not recognizing that digit extraction and sorting logic differ for negative values.

Key Takeaways

Radix Sort sorts numbers by processing each digit from least to most significant, using stable sorting at each step.

Stability in the digit sorting step is crucial to maintain correct order and achieve accurate final sorting.

Radix Sort is efficient for fixed-length integer keys and can outperform comparison sorts under the right conditions.

Handling different digit lengths and negative numbers requires special care to avoid incorrect results.

Understanding Radix Sort's mechanism and limitations helps choose the right sorting method for your data.

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