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

Коротко: Сортировка подсчётом и поразрядная сортировка работают без сравнений и потому могут быть быстрее O(n log n), если ключи — целые числа из небольшого диапазона.

Подробнее: Методы на сравнениях, такие как быстрая сортировка, никогда не могут быть лучше O(n log n). Использование свойств ключей обходит этот предел.

Подробности

• Сортировка подсчётом: Считает, сколько раз встречается каждое значение (массив размера k), вычисляет из этого начальные позиции и записывает элементы туда. Время O(n + k), устойчива.
• Предел: Если диапазон значений k огромен (например, 64-битные числа), массив подсчёта непригоден.
• Поразрядная сортировка: Сортирует по разрядам, от младшего к старшему, каждый раз устойчивым методом вроде сортировки подсчётом. Время O(d · (n + b)) при d разрядах и основании b.
• Пример: 32-битные числа с основанием 256: всего четыре прохода.
• Применение: Сортировка идентификаторов, почтовых индексов, строк фиксированной длины, графические конвейеры.
• Цена: Дополнительная память и зависимость от типа ключа.

См. также: O-нотация, Сортировка