Сортировка подсчётом

Идея

Если значения — целые числа из небольшого диапазона, сравнивать их вообще не нужно. Считаем, сколько раз встречается каждое значение, а затем для каждого значения вычисляем, сколько элементов не больше него — это ровно его последняя позиция в отсортированном массиве.

При k = max − min + 1 возможных значениях:

1. count[v] — сколько раз встречается v.
2. Префиксные суммы: count[v] = count[0] + … + count[v] — сколько элементов ≤ v.
3. Идём по входному массиву с конца и ставим каждое значение на позицию --count[v]. Проход с конца сохраняет порядок равных значений — сортировка устойчивая, на этом держится поразрядная сортировка.

Пример

Сортируем [2, 5, 3, 0, 2, 3, 0, 3] — пример из Кормена (значения 0…5).

Значение	0	1	2	3	4	5
count (сколько раз)	2	0	2	3	0	1
count (префиксные суммы)	2	2	4	7	7	8

Расставляем с конца: последняя 3 встаёт на позицию 7 − 1 = 6, последний 0 — на 2 − 1 = 1, следующая 3 — на 6 − 1 = 5, и так далее. Результат: 0, 0, 2, 2, 3, 3, 3, 5.

Попробуйте сами

Тот же пример по шагам. Измените данные или нажмите «Старт».

Псевдокод

COUNTING-SORT(A)
  min, max = minimum and maximum of A
  k = max − min + 1
  count[0..k − 1] = 0
  for each v in A
    count[v − min] = count[v − min] + 1
  for v = 1 to k − 1
    count[v] = count[v] + count[v − 1]
  for i = n − 1 downto 0
    v = A[i]
    count[v − min] = count[v − min] − 1
    B[count[v − min]] = v
  copy B to A

Сложность

Лучший	Средний	Худший	Память	Устойчивая	На месте
O(n + k)	O(n + k)	O(n + k)	O(n + k)	да	нет

• Линейное время при k = O(n). Это не противоречит нижней оценке Ω(n log n): она относится только к алгоритмам, которые сравнивают элементы.
• Память O(k) на счётчики — для значений вроде [0, 1 000 000 000] это гигабайты. Библиотека ограничивает k значением COUNTING_SORT_MAX_RANGE = 2²⁶ и выше бросает RangeError: для широких диапазонов используйте поразрядную сортировку.
• Только целые числа. 1.5, NaN или Infinity вызывают TypeError. Отрицательные значения допустимы — они сдвигаются на min.

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

Целые числа (или ключи, которые сводятся к целым: возраст, оценки, байты) в диапазоне, ненамного большем числа элементов. И как составная часть поразрядной сортировки.

Использование

import { countingSort } from 'ts-ds';

const grades = [4, 5, 3, 5, 2, 4, 5];
countingSort(grades); // [2, 3, 4, 4, 5, 5, 5]

Справочник API

Литература

• H. H. Seward, 1954 (магистерская диссертация, MIT).
• Кормен, §8.1 «Нижние оценки для сортировки» и §8.2 «Сортировка подсчётом».