Когда уместна сортировка подсчётом (counting sort)?

Counting sort хороша, когда сортируешь целые числа из небольшого диапазона (например, оценки 0–100, возраст, байты 0–255). Тогда она работает за O(n + k), где k это размер диапазона значений.

Когда НЕ подходит:

• значения это произвольные float или строки;
• диапазон огромный (например числа до миллиарда) — массив счётчиков на миллиард ячеек съест всю память;
• k сильно больше n, тогда O(n+k) проигрывает обычной O(n log n).

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

Короче: маленький диапазон целых — отлично, всё остальное — обычная сортировка.