Radix Sort Algorithm in DSA Python - 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. It starts sorting from the smallest digit (like the ones place) and moves to the largest digit (like the thousands place). Instead of comparing numbers directly, it groups them by each digit. This method works well when sorting many numbers with the same number of digits.

Why it matters

Without Radix Sort, sorting large lists of numbers can be slower because comparing whole numbers takes more time. Radix Sort speeds up sorting by breaking numbers into parts and sorting those parts quickly. This helps in areas like organizing phone numbers, sorting IDs, or processing large data sets efficiently.

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 numbers by digits instead of comparing whole values.

Think of it like...

Imagine sorting mail by zip code: 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, 90, 802 │
│ Sorted by 0:  │
│ 170, 90, 802 │
└───────────────┘

Step 2: Sort by next digit (tens place)
┌───────────────┐
│ 802, 2, 24   │
│ Sorted by 2:  │
│ 802, 2, 24   │
└───────────────┘

Step 3: Sort by most significant digit (hundreds place)
┌─────────────────────────────┐
│ 2, 24, 90, 170, 802         │
│ Sorted by 1:                │
│ 2, 24, 90, 170, 802         │
└─────────────────────────────┘

Build-Up - 6 Steps

1

Foundation

Understanding Digit-by-Digit Sorting

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

Imagine you have a list of numbers: [170, 45, 75, 90, 802, 24, 2, 66]. Instead of comparing whole numbers, Radix Sort looks at the digits in the ones place first. It groups numbers by their ones digit, then collects them back in order. Next, it looks at the tens place, groups again, and so on until all digits are processed.

Result

Numbers are partially sorted after each digit pass, moving closer to the final sorted list.

Understanding that sorting by each digit separately can lead to a fully sorted list is the key to grasping Radix Sort.

2

Foundation

Using Counting Sort as a Subroutine

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

Counting Sort is a simple sorting method that counts how many times each digit appears and uses that to place numbers in order. Radix Sort applies Counting Sort to each digit place, ensuring stable sorting (numbers with the same digit keep their order).

Result

Stable sorting by each digit ensures the overall order is correct after all digits are processed.

Knowing that Counting Sort is stable and fast for digits makes Radix Sort efficient and reliable.

3

Intermediate

Handling 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 digit lengths by treating missing digits as zero.

When numbers have different lengths, like 2 and 802, Radix Sort treats missing digits as zero during sorting. For example, 2 is treated as 002 when sorting by hundreds place. This keeps sorting consistent.

Result

Numbers with fewer digits are correctly placed relative to longer numbers.

Understanding how missing digits are handled prevents confusion about sorting numbers of varying lengths.

4

Intermediate

Implementing Radix Sort in Python

🤔Before reading on: Do you think Radix Sort requires comparing whole numbers directly? Commit to yes or no.

Concept: Radix Sort implementation processes digits using Counting Sort without direct number comparisons.

Here is a Python example: def counting_sort(arr, exp): n = len(arr) output = [0] * n count = [0] * 10 for i in range(n): index = (arr[i] // exp) % 10 count[index] += 1 for i in range(1, 10): count[i] += count[i - 1] i = n - 1 while i >= 0: index = (arr[i] // exp) % 10 output[count[index] - 1] = arr[i] count[index] -= 1 i -= 1 for i in range(n): arr[i] = output[i] def radix_sort(arr): max_num = max(arr) exp = 1 while max_num // exp > 0: counting_sort(arr, exp) exp *= 10 arr = [170, 45, 75, 90, 802, 24, 2, 66] radix_sort(arr) print(arr)

Result

[2, 24, 45, 66, 75, 90, 170, 802]

Knowing that Radix Sort avoids direct comparisons by sorting digits with Counting Sort clarifies its efficiency.

5

Advanced

Time Complexity and When Radix Excels

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

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

Radix Sort's time depends on the number of digits (d) and number of elements (n), roughly O(d*(n+k)) where k is digit range (usually 10). For fixed digit sizes, this is close to O(n). It beats comparison sorts like Quick Sort (O(n log n)) when digit count is small and data is large.

Result

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

Understanding the conditions where Radix Sort outperforms others helps choose the right sorting method.

6

Expert

Limitations and Variants of Radix Sort

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

Concept: Radix Sort can be adapted for strings and floats but requires special handling and variants.

For strings, Radix Sort processes characters from right to left, similar to digits. For floating-point numbers, it requires mapping to integers or handling sign and decimal parts carefully. Variants like LSD (least significant digit) and MSD (most significant digit) Radix Sort exist, each with tradeoffs.

Result

Radix Sort is versatile but needs careful adaptation for non-integer data.

Knowing Radix Sort's limits and variants prepares you for real-world data sorting challenges.

Under the Hood

Radix Sort works by repeatedly applying a stable sorting algorithm (like Counting Sort) to each digit place. It extracts digits using division and modulo operations, then sorts numbers based on those digits without comparing entire numbers. Stability ensures that the order from previous digit sorts is preserved, leading to a fully sorted list after all digits are processed.

Why designed this way?

Radix Sort was designed to avoid costly comparisons between large numbers by breaking them into smaller parts (digits). Early computers and data processing systems benefited from this approach because digit-based sorting could be done quickly and in parallel. Alternatives like comparison sorts were slower for large datasets with fixed digit sizes.

Input Array
  ↓
Extract Digit (ones place)
  ↓
Counting Sort by digit
  ↓
Partially Sorted Array
  ↓
Extract Next Digit (tens place)
  ↓
Counting Sort by digit
  ↓
Partially Sorted Array
  ↓
...
  ↓
Extract Most Significant Digit
  ↓
Counting Sort by digit
  ↓
Fully Sorted Array

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

Why it matters: Believing this leads to misunderstanding Radix Sort's efficiency and how it avoids costly comparisons.

Quick: Can Radix Sort sort any type of data without changes? Commit to yes or no.

Common Belief: Radix Sort works out of the box for all data types, including strings and floats.

Reality: Radix Sort needs adaptations to handle strings or floating-point numbers correctly.

Why it matters: Assuming universal applicability causes bugs or incorrect sorting results in real applications.

Quick: Is Radix Sort always faster than Quick Sort? 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 digit count is small and data size is large; otherwise, Quick Sort may be better.

Why it matters: Misusing Radix Sort on unsuitable data can lead to worse performance.

Quick: Does Radix Sort require extra memory proportional to input size? Commit to yes or no.

Common Belief: Radix Sort sorts in place without extra memory.

Reality: Radix Sort requires extra memory for temporary arrays during Counting Sort steps.

Why it matters: Ignoring memory needs can cause issues in memory-limited environments.

Expert Zone

1

Radix Sort's stability is crucial; losing stability breaks the sorting correctness after multiple digit passes.

2

Choosing between LSD and MSD Radix Sort affects performance and memory usage depending on data distribution.

3

Handling negative numbers requires offsetting or separate processing, which is often overlooked.

When NOT to use

Avoid Radix Sort when sorting data with very large digit ranges or variable-length keys without fixed maximum length. Use comparison-based sorts like Quick Sort or Merge Sort instead. For floating-point numbers or complex data types, specialized sorting algorithms or adaptations are better.

Production Patterns

Radix Sort is used in systems requiring fast integer sorting like database indexing, digital signal processing, and network packet sorting. It is often combined with other sorts for hybrid approaches, sorting small buckets with Quick Sort after Radix partitions.

Connections

Counting Sort

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

Understanding Counting Sort's stability and efficiency is key to grasping why Radix Sort works well.

Bucket Sort

Radix Sort and Bucket Sort both distribute elements into groups to sort efficiently.

Knowing how grouping reduces comparisons helps understand sorting optimizations across algorithms.

Human Sorting Processes

Radix Sort mirrors how humans sort items by multiple criteria step-by-step.

Recognizing this connection helps appreciate algorithm design inspired by natural problem-solving.

Common Pitfalls

#1 Sorting digits without stability breaks final order.

Wrong approach:

def counting_sort(arr, exp):
count = [0]*10
output = [0]*len(arr)
for num in arr:
index = (num // exp) % 10
count[index] += 1
for i in range(10):
count[i] = count[i] + count[i-1]
for num in arr:
index = (num // exp) % 10
output[count[index]-1] = num
count[index] -= 1
for i in range(len(arr)):
arr[i] = output[i]

Correct approach:

def counting_sort(arr, exp):
n = len(arr)
output = [0] * n
count = [0] * 10
for i in range(n):
index = (arr[i] // exp) % 10
count[index] += 1
for i in range(1, 10):
count[i] += count[i - 1]
i = n - 1
while i >= 0:
index = (arr[i] // exp) % 10
output[count[index] - 1] = arr[i]
count[index] -= 1
i -= 1
for i in range(n):
arr[i] = output[i]

Root cause:

Not iterating backwards during output placement breaks stability, causing incorrect final sorting.

#2 Ignoring numbers with fewer digits during sorting.

Wrong approach:

def radix_sort(arr):
max_num = max(arr)
exp = 1
while max_num // exp > 0:
counting_sort(arr, exp)
exp *= 10

arr = [170, 45, 75, 90, 802, 24, 2, 66]
radix_sort(arr)
print(arr)

Correct approach:

Same code works correctly because missing digits are treated as zero by integer division and modulo operations.

Root cause:

Misunderstanding that missing digits are implicitly handled leads to unnecessary code complexity or errors.

#3 Using Radix Sort on floating-point numbers without adaptation.

Wrong approach:

arr = [3.14, 2.71, 1.41]
radix_sort(arr)
print(arr)

Correct approach:

Convert floats to integers by scaling or use specialized float sorting algorithms before applying Radix Sort.

Root cause:

Radix Sort is designed for integers; applying it directly to floats causes incorrect sorting.

Key Takeaways

Radix Sort sorts numbers by processing each digit from smallest to largest place value.

It uses a stable sorting method like Counting Sort to sort digits without comparing whole numbers.

Radix Sort is efficient for large lists of numbers with fixed digit lengths but needs adaptations for other data types.

Stability and handling of different digit lengths are crucial for correct sorting.

Understanding Radix Sort's mechanism helps choose the right sorting algorithm for specific problems.

Practice

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

easy

A. Use a pivot to partition the list and sort partitions separately

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

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

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

Solution

1. Step 1: Understand Radix Sort approach

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

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 D

4. Quick Check:

   Radix Sort = Sort by digits from right to left [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 recursion

2. Which of the following is the correct way to initialize a list of empty buckets for Radix Sort in Python?

easy

A. buckets = [[]] * 10

B. buckets = [[] for _ in range(10)]

C. buckets = [0] * 10

D. buckets = list(range(10))

Solution

1. Step 1: Understand bucket initialization

   We need 10 separate empty lists (buckets) for digits 0-9, so list comprehension creates independent lists.

2. Step 2: Analyze options

   buckets = [[]] * 10 creates 10 references to the same list, causing bugs. buckets = [0] * 10 creates integers, not lists. buckets = list(range(10)) creates a list of numbers, not buckets.

3. Final Answer:

   buckets = [[] for _ in range(10)] -> Option B

4. Quick Check:

   Independent empty lists = list comprehension [OK]

Hint: Use list comprehension for independent empty lists [OK]

Common Mistakes:

• Using [[]] * 10 causes all buckets to reference the same list
• Initializing buckets with zeros instead of lists
• Confusing range with list of empty lists

3. What will be the output of the following Python code snippet implementing one pass of Radix Sort on the least significant digit?

arr = [170, 45, 75, 90, 802, 24, 2, 66]
buckets = [[] for _ in range(10)]
for num in arr:
    digit = num % 10
    buckets[digit].append(num)
result = []
for bucket in buckets:
    result.extend(bucket)
print(result)

medium

A. [170, 45, 75, 90, 802, 24, 2, 66]

B. [2, 802, 24, 45, 75, 66, 170, 90]

C. [170, 90, 802, 2, 24, 45, 75, 66]

D. [802, 2, 24, 45, 75, 66, 170, 90]

Solution

1. Step 1: Group numbers by least significant digit

   Digits are: 170(0), 45(5), 75(5), 90(0), 802(2), 24(4), 2(2), 66(6). Buckets: 0:[170,90], 2:[802,2], 4:[24], 5:[45,75], 6:[66].

2. Step 2: Concatenate buckets in order 0 to 9

   Result list is [170, 90] + [] + [802, 2] + [] + [24] + [45, 75] + [66] + [] + [] + [] = [170, 90, 802, 2, 24, 45, 75, 66].

3. Final Answer:

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

4. Quick Check:

   Sorted by last digit = [170, 90, 802, 2, 24, 45, 75, 66] [OK]

Hint: Group by digit, then join buckets in digit order [OK]

Common Mistakes:

• Mixing digit extraction (using // instead of %)
• Not preserving order inside buckets
• Concatenating buckets in wrong order

4. The following code attempts to perform Radix Sort but has a bug. What is the error?

def radix_sort(arr):
    max_num = max(arr)
    exp = 1
    while max_num // exp > 0:
        buckets = [[]] * 10
        for num in arr:
            index = (num // exp) % 10
            buckets[index].append(num)
        arr = []
        for bucket in buckets:
            arr.extend(bucket)
        exp *= 10
    return arr

print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))

medium

A. Using buckets = [[]] * 10 causes all buckets to reference the same list

B. The loop condition should be while max_num % exp > 0

C. The digit extraction formula is incorrect

D. The function does not return the sorted array

Solution

1. Step 1: Identify bucket initialization issue

   buckets = [[]] * 10 creates 10 references to the same list, so appending to one bucket appends to all.

2. Step 2: Check other parts

   Loop condition and digit extraction are correct. The function returns arr properly.

3. Final Answer:

   Using buckets = [[]] * 10 causes all buckets to reference the same list -> Option A

4. Quick Check:

   Bucket initialization = [[] for _ in range(10)] [OK]

Hint: Avoid [[]]*10; use list comprehension for buckets [OK]

Common Mistakes:

• Using [[]]*10 instead of list comprehension
• Changing loop condition incorrectly
• Misunderstanding digit extraction

5. You want to sort the list [329, 457, 657, 839, 436, 720, 355] using Radix Sort. After sorting by the least significant digit (units place), what will the list look like?

hard

A. [720, 355, 436, 457, 657, 329, 839]

B. [329, 720, 436, 457, 657, 839, 355]

C. [720, 329, 436, 839, 457, 657, 355]

D. [355, 720, 436, 329, 457, 657, 839]

Solution

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

   329(9), 457(7), 657(7), 839(9), 436(6), 720(0), 355(5).

2. Step 2: Group numbers by last digit and concatenate in digit order 0-9

   Digits 0:[720], 5:[355], 6:[436], 7:[457, 657], 9:[329, 839]. Concatenate: [720, 355, 436, 457, 657, 329, 839].

3. Final Answer:

   [720, 355, 436, 457, 657, 329, 839] -> Option A

4. Quick Check:

   Sorted by units digit = [720, 355, 436, 457, 657, 329, 839] [OK]

Hint: Sort by last digit, keep order inside groups [OK]

Common Mistakes:

• Mixing digit extraction with division instead of modulo
• Not preserving order of numbers with same digit
• Concatenating buckets in wrong digit order