Какой из известных алгоритмов сортировки можно считать самым быстрым на практике/в теории, и какова его сложность (средняя/худшая)?

Question

В теории для сортировок на сравнениях есть нижняя граница: в среднем нельзя лучше, чем O(n log n). Быстрые практические алгоритмы обычно тоже имеют среднюю O(n log n), но отличаются худшим случаем и константами. Quicksort часто очень быстрый на практике, но в худшем случае O(n^2). Поэтому в реальных библиотеках часто используют гибриды: например, в Python используется Timsort, который имеет худшую O(n log n) и может работать почти за O(n) на почти отсортированных данных.

YeaHub · Accepted Answer

“Самый быстрый” зависит от того, что именно сравниваем: теоретическую границу, гарантии худшего случая или реальную скорость на типичных данных.ОпределениеОпределение: Сортировка на сравнениях — сортировка, которая упорядочивает элементы, сравнивая их между собой (через <, >, ==).Теория: что быстрее O(n log n) (обычно) нельзяДля алгоритмов, которые сортируют только сравнениями, есть важный факт:В худшем/среднем случае требуется порядка n log n сравненийПоэтому “асимптотически быстрее” (например, O(n)) для общего случая на сравнениях получить нельзяПрактика: кто обычно самый быстрый1) Quicksort (быстрая сортировка)Средняя сложность: O(n log n)Худшая сложность: O(n^2)Почему быстрый:Хорошая локальность памятиМалые накладные расходыМинус: плохой случай возможен при неудачных опорных элементах2) Introsort (гибрид, часто в C++ std::sort)Идея:Стартуем как Quicksort (быстро в среднем)Если видим, что глубина рекурсии/разбиения становится подозрительной — переключаемся на HeapsortРезультат:Средняя: O(n log n)Худшая: O(n log n)На практике часто очень быстрый и при этом с гарантией худшего случая3) Timsort (в Python list.sort() и sorted())Это гибрид, оптимизированный под реальные данные:Худшая: O(n log n)На почти отсортированных данных может быть близко к O(n)Хорошо работает на данных с “кусками” упорядоченности (что часто встречается в жизни)Мини-пример в Python: почему “почти отсортировано” важноdata = list(range(10000))
data[5000], data[5001] = data[5001], data[5000]  # маленькое нарушение порядка

# Timsort обычно очень быстро обработает такой случай
sorted_data = sorted(data)
Когда бывают быстрее O(n log n)Если ключи ограничены по диапазону или структуре, можно использовать не “сортировку на сравнениях”:Counting sort: O(n + k) (k — диапазон значений)Radix sort: часто около O(n * d) (d — число “разрядов”)Но это не универсальная замена: нужны ограничения на данные.ВыводВ теории для универсальных сортировок на сравнениях “потолок” — O(n log n).На практике часто выигрывают гибриды: Timsort (Python) и Introsort (часто в стандартных библиотеках), потому что они сочетают скорость и гарантии.