Radix Sort

Radix Sort is a non-comparison-based sorting algorithm that sorts integers (or strings, depending on implementation) by processing individual digits or characters. It’s particularly efficient for data with a fixed length or when sorting large datasets with a limited range of keys. Radix Sort achieves a time complexity of O(d * (n + b)), where ( n ) is the number of elements, ( d ) is the number of digits, and ( b ) is the base (e.g., 10 for decimal numbers).

Radix Sort can be implemented using either Least Significant Digit (LSD) or Most Significant Digit (MSD) processing. In this explanation, we’ll focus on the more commonly used LSD approach, where sorting starts from the least significant digit and proceeds to the most significant.

Radix Sort: The Basics

Radix Sort works by:

1. Sorting by Each Digit: Sorting the numbers based on individual digits, starting with the least significant digit (rightmost) and moving left.

2. Stability Requirement: Radix Sort requires a stable sorting algorithm (like Counting Sort) for sorting digits, as it preserves the relative order of numbers with the same digit in the current place.

3. Digit-by-Digit Processing: After each digit-based sort, the array becomes partially sorted until all digits have been processed, resulting in a fully sorted array.

Key Concepts:

• Radix Sort does not use comparisons directly but rather relies on a stable sort for each digit.
• It is most effective when the number of digits (or characters) ( d ) is relatively small.

Time Complexity: - Best, Average, and Worst Case: O(d * (n + b)), where ( d ) is the number of digits and ( b ) is the base (typically 10 for decimal numbers). For integers with a fixed number of digits, this simplifies to O(n).

Space Complexity: O(n + b), as it requires temporary storage for stable sorting within each digit.

Stability: Radix Sort is a stable sorting algorithm, assuming the underlying sorting method for each digit is stable (like Counting Sort).

Radix Sort Algorithm Steps

1. Find the Maximum Value: Determine the maximum value in the array to know the number of digits to process.
2. Sort by Each Digit: Starting with the least significant digit, use a stable sort (e.g., Counting Sort) to sort the array based on each digit.
3. Repeat for Each Digit: Continue sorting by each successive digit until all digits have been processed.

Code Example: Radix Sort Using Counting Sort as a Stable Sort

from typing import List

def counting_sort_by_digit(arr: List[int], exp: int) -> None:
    """
    Perform counting sort on the array `arr` based on the digit represented by `exp`.
    - arr: List of integers to be sorted in place
    - exp: Exponent representing the current digit position (1, 10, 100, ...)
    """
    n = len(arr)
    output = [0] * n  # Output array to store sorted order
    count = [0] * 10  # Counting array for base 10 (digits 0 to 9)
    # Store count of occurrences in count array
    for num in arr:
        index = (num // exp) % 10
        count[index] += 1
    
    # Update count array to store cumulative counts
    for i in range(1, 10):
        count[i] += count[i - 1]
    
    # Build the output array by placing elements based on cumulative counts
    for i in range(n - 1, -1, -1):
        index = (arr[i] // exp) % 10
        output[count[index] - 1] = arr[i]
        count[index] -= 1
    
    # Copy sorted elements from output array back to original array
    for i in range(n):
        arr[i] = output[i]

def radix_sort(arr: List[int]) -> None:
    """
    Perform radix sort on the input array `arr`.
    - arr: List of non-negative integers to be sorted in place
    """
    if not arr:
        return
    # Find the maximum number to determine the number of digits
    max_val = max(arr)
    # Perform counting sort for each digit position (1, 10, 100, ...)
    exp = 1
    while max_val // exp > 0:
        counting_sort_by_digit(arr, exp)
        exp *= 10

# Example usage
arr = [170, 45, 75, 90, 802, 24, 2, 66]
radix_sort(arr)
print("Sorted array:", arr)
# Output: Sorted array: [2, 24, 45, 66, 75, 90, 170, 802]

Explanation of Code

Counting Sort by Digit:

• The counting_sort_by_digit function performs Counting Sort based on a specific digit, determined by exp (1 for units, 10 for tens, 100 for hundreds, etc.).
• It uses the digit at the exp position for sorting, leveraging Counting Sort’s stability to ensure correct placement of numbers.

Radix Sort:

• radix_sort finds the maximum value to determine the number of digits to process.
• For each digit (from least significant to most significant), it calls counting_sort_by_digit, sorting the array by each successive digit.

Example Execution: For an array [170, 45, 75, 90, 802, 24, 2, 66]:

1. Sort by units digit: [170, 90, 802, 2, 24, 45, 66, 75]
2. Sort by tens digit: [802, 2, 24, 45, 66, 170, 75, 90]
3. Sort by hundreds digit: [2, 24, 45, 66, 75, 90, 170, 802]