Counting Sort

Заводится массив-счётчик размера k, изначально заполненный нулями. За один проход по входу для каждого элемента x увеличивается count[x] — это ровно частота значения x. Затем массив восстанавливается проходом по count от 0 до k−1: значение v выписывается в результат count[v] раз подряд. Ни на одном шаге не задаётся вопрос "a < b?" — сравнения заменены прямой индексацией по значению, что и позволяет обойти доказанную в 2.2.1 границу Ω(n log n) (та теорема относится только к модели сравнений).A counter array of size k is created, initially all zeros. In one pass over the input, for each element x, count[x] is incremented — exactly the frequency of value x. The array is then reconstructed by walking count from 0 to k−1: value v is written to the result count[v] times in a row. At no step is "a < b?" ever asked — comparisons are replaced by direct indexing on the value, which is exactly what lets it beat the Ω(n log n) bound proven in 2.2.1 (that theorem only applies to the comparison model).

void counting_sort(std::vector<int>& a, int k) { // значения в [0, k)// values in [0, k)
    std::vector<int> count(k, 0);
    for (int x : a) count[x]++;              // O(n)
    int idx = 0;
    for (int v = 0; v < k; ++v)             // O(k)
        while (count[v]-- > 0) a[idx++] = v;
}

Эта прямая версия не сохраняет исходные объекты (только их числовые значения), что достаточно для сортировки чисел, но не подходит, если сортируются записи с дополнительными полями (нужна стабильность по ключу). Стабильная версия строит не сами значения, а массив префиксных сумм счётчика (count[v] становится "сколько элементов ≤ v"), затем проходит исходный массив справа налево, размещая каждый элемент по позиции из префиксной суммы и уменьшая её — эта версия сохраняет относительный порядок равных элементов и именно она используется как внутренний шаг radix sort (2.2.2.2), где стабильность обязательна.This direct version doesn't preserve the original objects (only their numeric values), which is enough for sorting numbers but not when records with extra fields are being sorted (stability by key is needed). The stable version instead builds a prefix-sum array of the counts (count[v] becomes "how many elements are ≤ v"), then walks the original array right to left, placing each element at the position given by the prefix sum and decrementing it — this version preserves the relative order of equal elements, and it's exactly this version that's used as radix sort's (2.2.2.2) inner step, where stability is mandatory.

Показана стабильная версия. Верхний ряд — вход. Средний ряд — счётчик count[v] (высота бара = частота значения v). Нижний ряд — результат. Красная рамка — элемент a[i], который сейчас обрабатывается (справа налево); жёлтая — ячейка счётчика, в которую он "смотрит".The stable version is shown. Top row — the input. Middle row — the counter count[v] (bar height = frequency of value v). Bottom row — the result. Red outline is the element a[i] being processed right now (right to left); yellow is the counter cell it's consulting.

O(n + k) выглядит линейным, но при k ≫ n (например, сортировка 100 чисел из диапазона [0, 10⁹)) память и время фактически определяются размером диапазона, а не количеством элементов — счётчик на миллиард ячеек ради сотни чисел практически бесполезен. Именно эту проблему решает radix sort (2.2.2.2), применяя counting sort многократно к отдельным разрядам вместо одного прохода по всему диапазону значений.O(n + k) looks linear, but when k ≫ n (e.g. sorting 100 numbers from the range [0, 10⁹)) memory and time are effectively dominated by the range's size, not the element count — a billion-cell counter for a hundred numbers is practically useless. This exact problem is solved by radix sort (2.2.2.2), applying counting sort repeatedly to individual digits instead of once over the whole value range.