Какие сортировки работают за линейное время и когда они применимы?

Counting sort и radix sort обходят нижнюю границу O(n log n), потому что не сравнивают элементы между собой, а используют структуру ключей.

Откуда граница O(n log n)

Любая сортировка сравнениями — дерево решений с n! листьями: его глубина не меньше log₂(n!) ≈ n log n. Обойти ограничение можно, только отказавшись от сравнений.

Counting sort

Считаем, сколько раз встречается каждое значение диапазона 0..k, затем восстанавливаем порядок префиксными суммами. Время O(n + k), память O(k). Эффективна, когда k сравнимо с n.

Radix sort

Сортируем по разрядам от младшего к старшему стабильной сортировкой (обычно counting sort). Время O(d·(n + b)), где d — число разрядов, b — основание. Подходит для целых чисел и строк фиксированной длины.

Когда не подходят

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

Коротко для собеседования

Counting и radix sort не сравнивают элементы, а раскладывают их по значениям ключей, поэтому обходят границу O(n log n). Применяйте их для целых чисел или строк фиксированной длины с небольшим диапазоном ключей; для произвольных объектов с компаратором выигрыша нет.