Radix sort is a linear sorting algorithm that works by distributing integers into buckets based on their digits, starting from the least significant digit to the most significant digit. It is a non-comparative sorting algorithm that can work efficiently for integers with a fixed number of digits. Radix sort uses the concept of bucket sort for each digit at each pass.

How Radix Sort Works

1. First, the input array is divided into individual digits or groups of digits, starting from the least significant digit. The number of digits considered depends on the range of values in the array.

2. Each digit or group of digits is iterated, and the integers are distributed into buckets based on that digit. Each bucket represents a range of values; for example, if we are considering the least significant digit (0-9) in base 10, there would be 10 buckets.

3. After distributing all the integers into buckets, the integers are collected back in the original order, combining the buckets.

4. Repeat the above steps for each remaining digit, moving from the least significant digit to the most significant digit.

5. Finally, after considering all the digits, the array is sorted in ascending order.

Example Implementation in Python

def radix_sort(arr):
    # Find the maximum number to determine the number of digits
    max_val = max(arr)
    num_digits = len(str(max_val))
    
    # Perform counting sort for each digit starting from the least significant digit
    for digit_index in range(num_digits):
        # Initialize the buckets
        buckets = [[] for _ in range(10)]
        
        # Distribute the integers into buckets based on the current digit
        for num in arr:
            digit = (num // (10 ** digit_index)) % 10
            buckets[digit].append(num)
            
        # Collect the integers from the buckets
        arr = [num for bucket in buckets for num in bucket]
        
    return arr

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

Time Complexity

The time complexity of radix sort is O(k * n), where n is the number of integers to be sorted and k is the number of digits in the maximum number. The number of passes through the array depends on the number of digits, which is usually small compared to the number of elements.

Conclusion

Radix sort is an efficient sorting algorithm for integers with a fixed number of digits. It avoids costly comparisons and instead utilizes bucketing and collecting based on digits. Due to its linear runtime complexity, it can be a favorable choice for sorting large sets of integers with a predictable range of values.

#techblog #radixsort