Поразрядная сортировка (radix)

Поразрядная сортировка сортирует числа по разрядам — от младшего к старшему — на каждом шаге применяя устойчивую сортировку подсчётом. Не использует сравнения элементов напрямую.

Сложность: время O(d · (n + k)), где d — число разрядов, k — основание системы счисления. Память: O(n + k). Хороша для целых чисел и строк фиксированной длины.

def radix_sort(a):
    if not a:
        return a
    max_val = max(a)
    exp = 1
    while max_val // exp > 0:
        buckets = [[] for _ in range(10)]
        for x in a:
            buckets[(x // exp) % 10].append(x)
        a = [x for b in buckets for x in b]
        exp *= 10
    return a