Radix Sort.

A Unique Linear-Time Sorting Algorithm

Sorting algorithms are essential in computer science, allowing us to organize data efficiently. While many popular sorting algorithms like Merge Sort, Heap Sort, and Quick Sort are comparison-based and have a lower bound of Ω(nLogn), Radix Sort takes a unique approach to achieve linear-time complexity under specific conditions.

Let’s delve into this fascinating algorithm, understand its mechanics, and explore its applications.

Why Do We Need Radix Sort?

Comparison-based sorting algorithms like Merge Sort or Quick Sort are efficient but have a fundamental limitation: \they can’t sort in less than Ω(nLogn) time. Counting Sort, a non-comparison-based algorithm, achieves linear time complexity O(n+k)O(n + k) for elements in a small range (1 to kk).

But what if the elements range from 1 to n2n^2?

Counting Sort becomes impractical here as its time complexity grows to O(n2)O(n^2), exceeding that of comparison-based algorithms. This is where Radix Sort comes to the rescue. By sorting numbers digit by digit, starting from the least significant digit (LSD) to the most significant digit (MSD), Radix Sort can handle larger ranges efficiently.

The Radix Sort Algorithm

Radix Sort uses Counting Sort (or any stable sort) as a subroutine. Here’s how it works:

Start with the least significant digit (LSD): Perform a stable sort based on this digit.
Move to the next significant digit: Repeat the sorting process for each subsequent digit until the most significant digit (MSD) is processed.

Example

Let’s sort the array [170,45,75,90,802,24,2,66] [170, 45, 75, 90, 802, 24, 2, 66]:

Sorting by the 1s place (LSD): Sorted array: [170,90,802,2,24,45,75,66] [170, 90, 802, 2, 24, 45, 75, 66] (802 precedes 2 because it appears earlier in the original list.)
Sorting by the 10s place: Sorted array: [802,2,24,45,66,170,75,90] [802, 2, 24, 45, 66, 170, 75, 90]
Sorting by the 100s place (MSD): Sorted array: [2,24,45,66,75,90,170,802] [2, 24, 45, 66, 75, 90, 170, 802]

Time Complexity of Radix Sort

Let dd represent the number of digits in the largest number and bb the base of the number system (e.g., 10 for decimals). The algorithm’s complexity is:

O(d×(n+b)) O(d \times (n + b))

For decimal numbers, b=10b = 10.
dd, the number of digits, is O(log⁡b(k)) O(\log_b(k)), where kk is the maximum value in the array.

For small kk values, Radix Sort’s time complexity becomes O(nlog⁡b(n)) O(n \log_b(n)). By increasing bb (e.g., setting b=nb = n), we can achieve O(n)O(n) complexity, making Radix Sort highly efficient for large ranges of integers.

Applications of Radix Sort

Radix Sort finds practical use in several areas:

Sorting Records by Multiple Fields: When records are keyed by multiple fields (e.g., sorting by year, then month, and finally day), Radix Sort can sort efficiently by processing each field in order.
Card Sorting Machines: Historically, Radix Sort was used in card sorting machines, where cards with punched holes were sorted column by column. Operators collected cards row by row, achieving accurate sorting.

Implementation in Python

Here’s a Python implementation of Radix Sort:

# Python program for implementation of Radix Sort

# A function to do counting sort of arr[] according to the digit represented by exp.
def countingSort(arr, exp1):
    n = len(arr)
    # The output array elements that will have sorted arr
    output = [0] * (n)
    # initialize count array as 0
    count = [0] * (10)
    # Store count of occurrences in count[]
    for i in range(0, n):
        index = (arr[i] / exp1)
        count[int((index) % 10)] += 1
    # Change count[i] so that count[i] now contains actual
    # position of this digit in output array
    for i in range(1, 10):
        count[i] += count[i - 1]
    # Build the output array
    i = n - 1
    while i >= 0:
        index = (arr[i] / exp1)
        output[count[int((index) % 10)] - 1] = arr[i]
        count[int((index) % 10)] -= 1
        i -= 1
    # Copying the output array to arr[],
    # so that arr now contains sorted numbers
    i = 0
    for i in range(0, len(arr)):
        arr[i] = output[i]

# Method to do Radix Sort
def radixSort(arr):
    # Find the maximum number to know number of digits
    max1 = max(arr)
    # Do counting sort for every digit. Note that instead
    # of passing digit number, exp is passed. exp is 10^i
    # where i is current digit number
    exp = 1
    while max1 // exp > 0:
        countingSort(arr, exp)
        exp *= 10

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

Summary

Radix Sort stands out for its ability to sort in linear time under certain conditions.
By leveraging stable sorts like Counting Sort and processing digits individually, it offers an elegant solution to handling large data ranges efficiently.
While it may not outperform comparison-based algorithms in all cases, its specialized approach makes it invaluable in scenarios involving multi-key sorting or large integer ranges.

Key Takeaways:

Radix Sort processes data digit by digit, starting from the least significant digit.
Its time complexity is O(d×(n+b))O(d \times (n + b)), and it achieves linear time when b=nb = n.
It’s suitable for scenarios like multi-field sorting and historical card sorting.

By understanding Radix Sort’s mechanics and applications, we gain a deeper appreciation for the diverse strategies available in algorithm design.