Mastering Radix Sort in Python: A Visual Guide

radix_sort.py

def radix_sort(arr):
    """
    Radix sort starting from the least significant digit(LSD)
    :param arr: The list needs to be sorted
    :return: A sorted list
    """
    # Find the maximum number of digits in the list
    max_digits = max([len(str(x)) for x in arr])

    # Set the base (radix) to 10
    base = 10

    # Create a list of bins to store the digits
    bins = [[] for _ in range(base)]

    # Iterate through each digit, starting with the least significant
    for i in range(0, max_digits):
        # Iterate through the elements in the list
        for x in arr:
            # Extract the i-th digit from the element
            # (starting from the rightest digit)
            digit = (x // base ** i) % base
            # Add the element to the bin for the i-th digit
            bins[digit].append(x)
        # Combine the bins back into the list, starting with the elements in the 0 queue
        arr = [x for queue in bins for x in queue]
        # Clear the bins for the next iteration
        bins = [[] for _ in range(base)]

    return arr


# Test the function
print(radix_sort([38, 2, 100, 5, 276, 42]))
# Output: [2, 5, 38, 42, 100, 276]

Thanks! Output of bins and arr on each iteration

-> [[100], [], [2, 42], [], [], [5], [276], [], [38], []]
         [100, 2, 42, 5, 276, 38]

-> [[100, 2, 5], [], [], [38], [42], [], [], [276], [], []]
         [100, 2, 5, 38, 42, 276]

-> [[2, 5, 38, 42], [100], [276], [], [], [], [], [], [], []]
         [2, 5, 38, 42, 100, 276]