Сортировки СравнениемComparison-Based Sorts

Ниже — минимальная сводка по каждому алгоритму (сложность, память, стабильность, идея в одно предложение); полный разбор с диаграммами, кодом и примерами — на отдельной странице по ссылке в названии.Below is a minimal summary of each algorithm (complexity, memory, stability, one-sentence idea); the full writeup with diagrams, code, and examples is on its own page via the name link.

Первые три — учебная база (одна и та же идея, разные компромиссы). Следующие три — способы гарантированно достичь Ω(n log n) (доказательство ниже), каждый со своим набором уступок по памяти, стабильности или предсказуемости худшего случая. Следующие два — гибриды, которыми реально пользуются стандартные библиотеки: IntroSort лежит в основе std::sort, Timsort — в основе sorted() в Python и Arrays.sort() для объектов в Java. Последние семь карточек (2.2.1.9–2.2.1.15, пока без ссылок) — второстепенные варианты и алгоритмы из других моделей вычислений: Shell/Cocktail/Comb/Gnome — небольшие модификации уже разобранных O(n²)-алгоритмов; Bitonic Sort и Odd-Even Mergesort — сортирующие сети с фиксированной, независимой от данных схемой сравнений (модель, ориентированная на параллельное железо, а не последовательное сравнение); External Merge Sort — тот же merge sort, но в модели, где доминирует стоимость обращения к диску, а не число сравнений в памяти.The first three are the textbook baseline (the same idea, different trade-offs). The next three are ways to guarantee Ω(n log n) (proof below), each with its own concession on memory, stability, or worst-case predictability. The next two are hybrids actually used by standard libraries: IntroSort underlies std::sort, Timsort underlies Python's sorted() and Java's Arrays.sort() for objects. The last seven cards (2.2.1.9–2.2.1.15, not yet linked) are minor variants and algorithms from other computational models: Shell/Cocktail/Comb/Gnome are small tweaks on the O(n²) algorithms already covered; Bitonic Sort and Odd-Even Mergesort are sorting networks with a fixed, data-independent comparison schedule (a model aimed at parallel hardware rather than sequential comparison); External Merge Sort is the same merge sort, but in a model where disk-access cost dominates rather than the number of in-memory comparisons.

Утверждение "любая сортировка сравнением требует Ω(n log n) сравнений в худшем случае" — не эмпирическое наблюдение, а доказанная теорема, и доказательство удивительно простое. Любой алгоритм сортировки сравнением можно представить как дерево решений (decision tree): каждый внутренний узел — это одно сравнение "a[i] < a[j]?", каждый лист — одна из n! возможных перестановок входа (тот порядок, в который алгоритм в итоге расставит элементы). Чтобы дерево умело различить все n! перестановок, у него должно быть как минимум n! листьев.The claim "any comparison-based sort requires Ω(n log n) comparisons in the worst case" isn't an empirical observation but a proven theorem, and the proof is surprisingly simple. Any comparison-based sorting algorithm can be modeled as a decision tree: every internal node is one comparison "a[i] < a[j]?", every leaf is one of the n! possible input permutations (the order the algorithm ultimately arranges the elements into). For the tree to be able to distinguish all n! permutations, it must have at least n! leaves.

Бинарное дерево высоты h имеет не более 2^h листьев, значит для n! листьев нужна высота h ≥ log₂(n!). По формуле Стирлинга log₂(n!) = Θ(n log n) — то есть любое дерево решений, различающее n! перестановок, имеет высоту Ω(n log n), а высота дерева — это в точности число сравнений в худшем случае вдоль самого длинного пути от корня до листа. Отсюда: ни один алгоритм, использующий только сравнения "меньше/больше", не может гарантированно сортировать быстрее, чем за Ω(n log n) в худшем случае — это не ограничение конкретных алгоритмов (quicksort, merge sort), а фундаментальный предел самой модели вычисления.A binary tree of height h has at most 2^h leaves, so n! leaves require height h ≥ log₂(n!). By Stirling's formula, log₂(n!) = Θ(n log n) — meaning any decision tree distinguishing n! permutations has height Ω(n log n), and a tree's height is exactly the number of comparisons in the worst case along the longest root-to-leaf path. Hence: no algorithm using only "less-than/greater-than" comparisons can guarantee sorting faster than Ω(n log n) in the worst case — this isn't a limitation of specific algorithms (quicksort, merge sort) but a fundamental limit of the computational model itself.

Это же объясняет, почему следующая тема (2.2.2) вообще существует: единственный способ обойти Ω(n log n) — выйти за пределы модели "только сравнения" и использовать структуру самих значений (например, что они целые числа в известном диапазоне). Counting sort, radix sort и bucket sort делают именно это — они не сортировки сравнением, поэтому теорема о нижней границе на них не распространяется.This also explains why the next topic (2.2.2) exists at all: the only way around Ω(n log n) is to step outside the "comparisons only" model and exploit the structure of the values themselves (e.g. that they're integers in a known range). Counting sort, radix sort, and bucket sort do exactly that — they aren't comparison-based sorts, so the lower-bound theorem doesn't apply to them.