Radix Sort Using Python

Radix sort is an efficient sorting algorithm that works by sorting the elements of the list based on their digits or individual digits in their binary representation. It is a stable sorting algorithm, which means that the relative order of elements with the same value is preserved in the sorted list.

Radix sort is a useful algorithm when the elements of the input list are small integers and the number of digits is not too large. It has a time complexity of O(d(n+b)), where d is the number of digits, n is the length of the input list, and b is the base used for representing the numbers (for example, b = 10 for decimal numbers and b = 2 for binary numbers).

Here is an implementation of radix sort in Python:

def radix_sort(arr, base=10):
    # Find the maximum number of digits
    max_digits = max([len(str(x)) for x in arr])
    
    # Sort the elements by each digit
    for i in range(max_digits):
        # Create a list of lists to store the elements by digit
        buckets = [[] for _ in range(base)]
        
        # Distribute the elements into the buckets
        for x in arr:
            digit = (x // base**i) % base
            buckets[digit].append(x)
        
        # Concatenate the buckets to obtain the sorted list
        arr = [x for bucket in buckets for x in bucket]
    
    return arr

# Test the function
arr = [170, 45, 75, 90, 802, 24, 2, 66]
print(radix_sort(arr))  # Output: [2, 24, 45, 66, 75, 90, 170, 802]

In this implementation, the function first finds the maximum number of digits among the elements of the input list, and then sorts the elements by each digit using a list of lists (buckets) to store the elements by digit. The elements are distributed into the buckets based on their digit, and then the buckets are concatenated to obtain the sorted list.

Radix sort is a stable and efficient sorting algorithm when the number of digits is small, but it is not suitable for sorting large lists or lists with a large number of digits, because it requires additional space to store the buckets and the time complexity is linear in the number of digits.

Using Recursion

Radix sort can also be implemented using recursion, by dividing the input list into smaller sublists and sorting each sublist using radix sort. Here is an example of a recursive implementation of radix sort in Python:

def radix_sort_recursive(arr, base=10):
    # Base case: the list has only one element
    if len(arr) == 1:
        return arr
    
    # Divide the input list into two sublists
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
    
    # Sort the sublists recursively
    left = radix_sort_recursive(left, base)
    right = radix_sort_recursive(right, base)
    
    # Merge the sorted sublists
    sorted_arr = []
    i, j = 0, 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            sorted_arr.append(left[i])
            i += 1
        else:
            sorted_arr.append(right[j])
            j += 1
    sorted_arr.extend(left[i:])
    sorted_arr.extend(right[j:])
    
    return sorted_arr

# Test the function
arr = [170, 45, 75, 90, 802, 24, 2, 66]
print(radix_sort_recursive(arr))  # Output: [2, 24, 45, 66, 75, 90, 170, 802]

This recursive implementation of radix sort works by dividing the input list into two sublists, sorting.