Может ли сортировка быть быстрее чем O(n log n)

Что проверяют

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

Как отвечать

Начните с точной формулировки: нижняя граница Ω(n log n) действует для сортировок сравнением в худшем случае. Доказательство через дерево решений: способов упорядочить n элементов n!, каждое сравнение делит их максимум надвое, значит нужно не меньше log₂(n!) сравнений, а это порядка n log n. Обойти границу можно двумя путями.

Первый: не сравнивать элементы, а использовать их структуру.

• сортировка подсчётом: O(n + k), где k это размер диапазона значений. Хороша, когда k сопоставимо с n, например возраст или оценки от 1 до 100;
• поразрядная (radix): O(d · (n + b)), где d это число разрядов, b основание. Подходит для целых чисел фиксированной длины и строк одинаковой длины;
• блочная (bucket): в среднем O(n), если значения равномерно распределены по диапазону. На перекошенных данных деградирует.

Второй: удачные входные данные. Сортировка вставками и TimSort на уже упорядоченном массиве работают за O(n), но гарантия в худшем случае у TimSort остаётся O(n log n), а у вставок и вовсе O(n²).

Привяжите к Java. Arrays.sort для примитивов использует Dual-Pivot Quicksort, для объектов и Collections.sort стабильный TimSort, который находит уже отсортированные участки и на почти упорядоченных данных близок к линейному. Для больших byte[], short[] и char[] JDK сам переключается на сортировку подсчётом: диапазон значений там маленький.

Где спотыкаются

Говорят «быстрее O(n log n) нельзя» без оговорки про сравнения. Интервьюер ждёт именно этого уточнения, без него ответ считается неверным.

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

Путают асимптотику и реальную скорость. Radix с большим d или bucket на неудачном распределении на практике часто медленнее Arrays.sort, у которого малые константы и хорошая работа с кэшем процессора.