Сортировка подсчётом: как работает и почему быстрее O(n log n)

Коротко

Это сортировка, которая работает за линейное время — быстрее теоретического предела O(n log n). Ниже разберём, почему это не жульничество.

Идея: не сравнивать, а считать

Все привычные сортировки — пузырьком, слиянием, быстрая — построены на сравнениях: «этот элемент больше того?». Для таких алгоритмов доказано, что быстрее O(n log n) не получится.

Сортировка подсчётом обходит этот предел, потому что не делает ни одного сравнения элементов между собой. Вместо этого она считает, сколько раз встретилось каждое значение, а потом восстанавливает массив по счётчикам.

Аналогия: вам нужно расставить по возрастанию сто карточек с оценками от 1 до 5. Можно попарно сравнивать — а можно просто разложить на пять стопок, а потом собрать стопки по порядку. Второй способ и есть сортировка подсчётом.

Как это работает по шагам

Возьмём массив [4, 2, 2, 8, 3, 3, 1].

Шаг 1. Считаем количество каждого значения.

значение:  0  1  2  3  4  5  6  7  8
счётчик:   0  1  2  2  1  0  0  0  1

Шаг 2. Собираем результат. Проходим по счётчикам слева направо и выписываем каждое значение столько раз, сколько оно встретилось:

1 (×1), 2 (×2), 3 (×2), 4 (×1), 8 (×1)
→ [1, 2, 2, 3, 3, 4, 8]

Всё. Массив отсортирован, и мы не сравнили ни одной пары.

Простая версия на Python

def counting_sort_simple(arr: list[int]) -> list[int]:
    if not arr:
        return arr

    low, high = min(arr), max(arr)
    counts = [0] * (high - low + 1)

    # шаг 1: считаем вхождения
    for num in arr:
        counts[num - low] += 1

    # шаг 2: разворачиваем счётчики обратно в массив
    result = []
    for value, count in enumerate(counts):
        result.extend([value + low] * count)

    return result


print(counting_sort_simple([4, 2, 2, 8, 3, 3, 1]))
# [1, 2, 2, 3, 3, 4, 8]

Сдвиг на low позволяет работать с отрицательными числами и не тратить память на пустой диапазон: для массива [100, 102, 101] мы создадим счётчик на 3 ячейки, а не на 103.

Устойчивая версия

Простая версия выше не сохраняет исходный порядок равных элементов — она их просто пересоздаёт. Для чисел это незаметно, но если сортируются объекты по ключу, порядок важен.

Устойчивая реализация использует префиксные суммы: сначала считаем, сколько элементов должно стоять до каждого значения, и заполняем результат, проходя исходный массив справа налево.

def counting_sort_stable(arr: list[int]) -> list[int]:
    if not arr:
        return arr

    low, high = min(arr), max(arr)
    counts = [0] * (high - low + 1)

    for num in arr:
        counts[num - low] += 1

    # превращаем счётчики в позиции: counts[i] = сколько элементов <= i
    for i in range(1, len(counts)):
        counts[i] += counts[i - 1]

    result = [0] * len(arr)

    # идём с конца — это и обеспечивает устойчивость
    for num in reversed(arr):
        counts[num - low] -= 1
        result[counts[num - low]] = num

    return result

Почему обход с конца сохраняет порядок: последний из равных элементов занимает самую правую свободную позицию, предпоследний — следующую слева, и так далее. Исходная последовательность восстанавливается точно.

Именно эта версия используется как строительный блок внутри поразрядной сортировки, где устойчивость обязательна.

Почему это не противоречит теории

Нижняя граница O(n log n) доказана только для сортировок сравнением. Такой алгоритм можно представить деревом решений: каждое сравнение — развилка. Чтобы различить все n! возможных перестановок, дереву нужна глубина не меньше log₂(n!) ≈ n log n.

Сортировка подсчётом использует дополнительное знание — что элементы это целые числа из известного диапазона. Она не различает перестановки через сравнения, а сразу вычисляет позицию по значению. Это другой класс алгоритмов, и граница на него не распространяется.

Где подвох: цена памяти

Сложность O(n + k) выглядит прекрасно, пока k мал. Но k — это диапазон значений, а не количество элементов.

# отлично: k = 100
counting_sort_simple([5, 3, 99, 1] * 1000)

# катастрофа: k = 1_000_000_000
counting_sort_simple([1, 1_000_000_000])
# попытается создать список на миллиард элементов

Правило простое: сортировка подсчётом выгодна, когда k сравнимо с n или меньше. Если диапазон значений сильно больше количества элементов, обычная быстрая сортировка окажется и быстрее, и экономнее.

Когда применять

Хорошие случаи:

• оценки, баллы, возраст, рейтинг — небольшой известный диапазон;
• сортировка байтов (k = 256) — классическое применение;
• подсчёт символов в строке, например для проверки анаграмм;
• как внутренний шаг поразрядной сортировки.

Плохие случаи:

• вещественные числа — счётчик по ним не построить;
• произвольные строки;
• большие целые числа с редкими значениями;
• данные, у которых нет естественного целочисленного ключа.

Сравнение с сортировками сравнением

Частые ошибки

Забытый сдвиг на минимум. Без него отрицательные числа дадут отрицательный индекс, а массив с большими значениями съест лишнюю память.

Проход слева направо в устойчивой версии. Порядок равных элементов перевернётся, и устойчивость пропадёт — при этом сам массив останется корректно отсортированным, поэтому ошибку легко не заметить.

Применение без оценки диапазона. Самая опасная. Код проходит тесты на маленьких данных, а в продакшене пытается выделить гигабайты. Всегда проверяйте max - min до создания массива счётчиков.

Что запомнить

• Сортировка подсчётом не сравнивает элементы, а считает их вхождения.
• O(n + k) — линейно, но k это диапазон значений, а не размер массива.
• Не противоречит границе O(n log n), потому что не относится к сортировкам сравнением.
• Устойчивость достигается префиксными суммами и обходом исходного массива с конца.
• Применима только к целым числам из ограниченного диапазона.

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→