Сортировка подсчётом (counting sort)

Сортировка подсчётом не сравнивает элементы, а подсчитывает, сколько раз встречается каждое значение, и восстанавливает массив по этим частотам. Работает только для целых чисел в ограниченном диапазоне [0, k].

Сложность: время O(n + k), где k — размер диапазона значений. Память: O(n + k). Эффективна, когда k не сильно превышает n; может быть устойчивой.

def counting_sort(a):
    if not a:
        return a
    k = max(a)
    count = [0] * (k + 1)
    for x in a:
        count[x] += 1
    res = []
    for value, c in enumerate(count):
        res.extend([value] * c)
    return res