Сортировки за линейное время: Как преодолеть предел O(N log N)
В любом классическом учебнике по алгоритмам написано, что лучшая возможная сложность для сортировки массива — это O(N log N). Эту асимптотику выдают быстрая сортировка (QuickSort) и сортировка слиянием (MergeSort). В дискретной математике существует строгое доказательство того, что сортировки, основанные на сравнении элементов, физически не могут работать быстрее. Но что, если мы откажемся от операций сравнения? Здесь на сцену выходят алгоритмы сортировки за линейное время O(N).
Математическое доказательство предела O(N log N) базируется на деревьях решений. Любой алгоритм сортировки сравнениями можно представить как бинарное дерево, где каждый узел — это вопрос «A меньше B?», а листья — все возможные перестановки исходного массива. Для массива из N элементов существует N! (факториал) уникальных перестановок. Высота такого бинарного дерева (максимальное количество сравнений) по формуле Стирлинга не может быть меньше математической границы Ω(N log N).
Однако этот барьер можно обойти, если мы заранее знаем свойства сортируемых данных. Если наши данные — это целые числа в ограниченном диапазоне, мы можем использовать Сортировку подсчетом (Counting Sort). Идея гениально проста: вместо того, чтобы сравнивать числа друг с другом, мы создаем вспомогательный массив-счетчик (размером, равным максимальному числу) и просто один раз проходим по данным, увеличивая счетчик по индексу, равному самому числу. Затем мы собираем отсортированный массив, просто распечатывая индексы счетчика нужное количество раз. Сложность алгоритма составит O(N + K), где K — размер диапазона.
Если диапазон K слишком велик (например, мы сортируем 32-битные числа, и массив-счетчик на 4 миллиарда элементов не поместится в оперативной памяти), на помощь приходит Поразрядная сортировка (Radix Sort). Этот алгоритм разбивает числа на разряды (например, единицы, десятки, сотни) и сортирует массив несколько раз устойчивой сортировкой (тем же Counting Sort), начиная с младшего разряда к старшему (метод LSD). Асимптотика становится равной O(d * (N + b)), где d — количество разрядов, а b — основание системы счисления.
Почему же линейные сортировки не используются по умолчанию в стандартных библиотеках (например, в функции `std::sort` в C++ или `Arrays.sort` в Java)? Ответ кроется в архитектуре современных процессоров. Несмотря на лучшую математическую асимптотику, линейные сортировки требуют выделения дополнительной памяти, а их шаблоны доступа к памяти хаотичны, что приводит к постоянным промахам кэша (Cache Miss). Быстрая сортировка (QuickSort), работая "на месте" (in-place), максимально эффективно использует кэш-линии процессора L1/L2, из-за чего на реальном железе она обгоняет Radix Sort в подавляющем большинстве задач.
