Radix Sort

---

Radix Sort is a non-comparison-based sorting algorithm that sorts numbers digit by digit, starting from the least significant digit (LSD) or the most significant digit (MSD). It is particularly efficient when dealing with large datasets of integers or strings, where the range of the digits is limited, such as in cases where the numbers have fixed length or the number of possible digits is small.

Radix Sort operates by processing each digit of the numbers, distributing them into buckets based on that digit, and then recombining them. This process is repeated for each digit until all the digits have been processed.

---

What is Radix Sort?

Radix Sort is a linear time complexity sorting algorithm that can sort integers or strings by processing each digit or character separately. It works by first sorting the input by the least significant digit (LSD) and then proceeding to the next more significant digit. This process is repeated until all digits have been processed.

The sorting is done using a stable sub-sorting algorithm, such as Counting Sort, to arrange the elements based on each individual digit.

Key Properties of Radix Sort:

• Non-comparison-based: Radix Sort does not compare elements directly; instead, it sorts based on individual digits.
• Stable Sort: Radix Sort is stable, meaning elements with the same digit at the current position retain their relative order from previous rounds.
• Efficient for Large Data: Radix Sort is efficient when sorting large datasets, especially when the number of digits (or character positions) is smaller than the number of items being sorted.
• Applicable to Integers and Strings: Radix Sort can be used to sort both integers and strings by sorting each digit or character separately.

---

How Does Radix Sort Work?

Radix Sort works by sorting the input list multiple times, each time focusing on a different digit (or character) position. Here's how it works step by step:

1. Start with the Least Significant Digit (LSD): Begin by sorting the input based on the least significant digit (the rightmost digit).
2. Stable Sorting: Use a stable sub-sorting algorithm, like Counting Sort, to sort the input based on the current digit. Stability ensures that elements with the same digit stay in their relative order.
3. Move to the Next Digit: After sorting by the least significant digit, move to the next digit (more significant) and repeat the sorting process.
4. Repeat Until All Digits Are Processed: Continue this process for each digit or character position until the most significant digit (leftmost) is processed.

The key to Radix Sort is that each pass over the data only sorts based on one digit, and after several passes, the data is sorted as a whole.

---

Radix Sort: Python Code Implementation

Here is a Python implementation of Radix Sort for sorting integers:

# Counting Sort to sort elements based on a specific digit
def counting_sort(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10  # There are 10 possible digits (0-9)

    # Count the occurrences of each digit
    for i in range(n):
        index = arr[i] // exp
        count[index % 10] += 1

    # Change count[i] to represent the actual position of this digit in output[]
    for i in range(1, 10):
        count[i] += count[i - 1]

    # Build the output array based on the count positions
    i = n - 1
    while i >= 0:
        index = arr[i] // exp
        output[count[index % 10] - 1] = arr[i]
        count[index % 10] -= 1
        i -= 1

    # Copy the sorted output array back to the original array
    for i in range(n):
        arr[i] = output[i]

# Main function to implement Radix Sort
def radix_sort(arr):
    # Find the maximum number to determine the number of digits
    max_val = max(arr)

    # Perform counting sort for every digit (exp is 10^i, i is the digit index)
    exp = 1
    while max_val // exp > 0:
        counting_sort(arr, exp)
        exp *= 10

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

Output:

Unsorted Array: [170, 45, 75, 90, 802, 24, 2, 66]
Sorted Array: [2, 24, 45, 66, 75, 90, 170, 802]

Explanation of Code:

• Counting Sort: The function counting_sort is used as a subroutine to sort the array based on the current digit (given by the exp parameter). This ensures that sorting is stable.
• Radix Sort: The radix_sort function finds the maximum value in the input array to determine the number of digits. It then iteratively sorts the array based on each digit, using Counting Sort for each digit position.

---

Time and Space Complexity of Radix Sort

Time Complexity:

• Best, Average, and Worst Case: $O(n\cdot k)$, where n is the number of elements in the input array and k is the number of digits in the largest number. The time complexity remains linear in terms of the number of digits for each pass and the number of elements.
  • For integers with d digits, the time complexity is $O(d\cdot n)$, where d is the number of digits, and n is the number of elements.
  • If the number of digits is fixed or small compared to the input size, Radix Sort performs efficiently.

Space Complexity:

• Space Complexity: $O(n+k)$, where n is the number of elements, and k is the range of possible digit values (e.g., 10 for decimal numbers, 256 for ASCII characters). The extra space is required for the counting array and output array.

---

Advantages of Radix Sort

1. Efficient for Large Datasets: Radix Sort performs well on large datasets, especially when the range of digits is relatively small.
2. Linear Time Complexity: Radix Sort can achieve linear time complexity, O(n \cdot k), which is faster than comparison-based sorting algorithms like Merge Sort or QuickSort in some cases.
3. Stable Sorting: Radix Sort is a stable sorting algorithm, which is useful when maintaining the relative order of equal elements is important.

---

Disadvantages of Radix Sort

1. Limited to Integers or Fixed-Length Strings: Radix Sort is mainly used for sorting integers or fixed-length strings. It is not suitable for sorting arbitrary data types.
2. Requires Extra Space: The algorithm requires additional memory for the counting array and output array, which may be a drawback for memory-constrained systems.
3. Performance Dependent on Number of Digits: Radix Sort's efficiency depends on the number of digits in the largest number. If the number of digits is large, Radix Sort might become less efficient compared to comparison-based algorithms.

---

When to Use Radix Sort?

1. Large Integers or Fixed-Length Strings: Radix Sort is ideal for sorting large datasets of integers or strings where the range of values (i.e., the number of digits or characters) is not too large.
2. Stable Sorting Needed: When a stable sort is required (i.e., maintaining the relative order of equal elements), Radix Sort is a good choice.
3. When Performance is Key: Radix Sort is an efficient choice when the number of digits or characters is small relative to the number of elements, as it can operate in linear time.

---

---