this is a pure python implementation of the radix sort algorithm source https en wikipedia orgwikiradixsort examples radixsort0 5 3 2 2 0 2 2 3 5 radixsortlistrange15 sortedrange15 true radixsortlistrange14 1 1 sortedrange15 true radixsort1 100 10 1000 sorted1 100 10 1000 true declare and initialize empty buckets split listofints between the buckets put each buckets contents into listofints move to next examples radix_sort 0 5 3 2 2 0 2 2 3 5 radix_sort list range 15 sorted range 15 true radix_sort list range 14 1 1 sorted range 15 true radix_sort 1 100 10 1000 sorted 1 100 10 1000 true declare and initialize empty buckets split list_of_ints between the buckets put each buckets contents into list_of_ints move to next
from __future__ import annotations

RADIX = 10


def radix_sort(list_of_ints: list[int]) -> list[int]:
    
    placement = 1
    max_digit = max(list_of_ints)
    while placement <= max_digit:
        
        buckets: list[list] = [[] for _ in range(RADIX)]
        
        for i in list_of_ints:
            tmp = int((i / placement) % RADIX)
            buckets[tmp].append(i)
        
        a = 0
        for b in range(RADIX):
            for i in buckets[b]:
                list_of_ints[a] = i
                a += 1
        
        placement *= RADIX
    return list_of_ints


if __name__ == "__main__":
    import doctest

    doctest.testmod()