Сортировки: от пузырька до Timsort и radix

Сортировка — самый изученный алгоритмический сюжет в информатике, и это не случайность. Дональд Кнут посвятил ей целый том «Искусства программирования», а Кормен с соавторами вынесли её в первые главы CLRS. Причина простая: сортировка — это не столько задача, сколько предобработка. Отсортированные данные превращают линейный поиск в логарифмический (бинарный поиск), задачу «найти дубликаты» — в один проход, задачу «пересечь два множества» — в два указателя, а множество жадных алгоритмов вообще начинаются со слова «отсортируем». Поэтому вопрос «какую сортировку писать» на практике почти всегда имеет ответ «встроенную». Но чтобы пользоваться встроенной осознанно — понимать, почему list.sort() летает на почти отсортированных данных, почему Java иногда бросает Comparison method violates its general contract! и почему замена сравнения на radix ускоряет пайплайн втрое — нужно знать, что там внутри. Асимптотикой и техникой инвариантов из статьи Анализ алгоритмов дальше пользуемся свободно.

Карта территории

Четыре свойства, по которым сортировки реально различают

Асимптотика — только одна ось; в инженерных решениях чаще важны другие четыре.

Устойчивость (stability). Сортировка устойчива, если элементы с равными ключами сохраняют относительный порядок. Это не эстетика: устойчивость позволяет сортировать по нескольким ключам последовательными проходами. Хотите таблицу «по отделу, внутри отдела по зарплате»? Отсортируйте по зарплате, потом устойчиво по отделу — и всё сойдётся. Без устойчивости придётся писать составной компаратор.

Работа на месте (in-place). Сколько дополнительной памяти нужно сверх входного массива. Quicksort — O(log n) на стек рекурсии, heapsort — O(1), классический merge sort — O(n) на буфер. На 8 ГБ входных данных разница между O(1) и O(n) — это разница между «работает» и «OOM».

Адаптивность. Умеет ли алгоритм извлекать выгоду из уже существующего порядка. Реальные данные почти никогда не случайны: логи почти отсортированы по времени, дозагруженный список — это отсортированный префикс плюс хвост, результат из БД приходит частично упорядоченным. Timsort на таких данных даёт O(n), а обычный merge sort — честные n log n.

Число сравнений vs число перемещений. Если сравнение дёшево (int), а элемент тяжёлый (структура на 200 байт) — важны перемещения. Если наоборот (сравнение строк по локали, вызов через указатель на функцию) — важны сравнения. Отсюда трюк «сортируем массив индексов, потом переставляем один раз».

Почему O(n log n) — это стена (для сравнений)

Утверждение: любой детерминированный алгоритм, получающий информацию о порядке только через попарные сравнения, в худшем случае делает Ω(n log n) сравнений. Доказательство занимает пять строк. Представим работу алгоритма как дерево решений: внутренний узел — сравнение a[i] < a[j], две ветви — два исхода, лист — выдаваемая перестановка. Чтобы алгоритм был корректен, каждая из n! перестановок входа должна приводить в свой лист — иначе два разных входа получили бы одинаковый ответ, и хотя бы для одного он неверен.

Дерево бинарное, листьев не меньше n!, значит его высота h ≥ log₂(n!). По формуле Стирлинга log₂(n!) = n log₂ n − n log₂ e + O(log n) = Θ(n log n). Высота дерева — это и есть худшее число сравнений. Готово. Три следствия: (1) merge sort и heapsort оптимальны с точностью до константы — улучшить их асимптотику принципиально невозможно; (2) граница касается только модели сравнений, а counting и radix читают ключ как число, поэтому O(n) там достижимо; (3) граница — про худший случай, и если вход структурирован (почти отсортирован), информация о порядке частично «бесплатна» — адаптивные алгоритмы вроде Timsort законно уходят ниже, вплоть до O(n).

Квадратичные: не мусор, а базовый блок

Пузырёк

Пузырёк раз за разом проходит по массиву и меняет местами соседей, стоящих не в том порядке. Инвариант: после i-го прохода суффикс длины i содержит i наибольших элементов на своих финальных местах — отсюда и внутренний цикл до n − 1 − i. Сравнение делают строгим (a[j] > a[j+1]), иначе теряется устойчивость, а флаг «был ли обмен» даёт досрочный выход и O(n) на отсортированном входе.

Число обменов ровно равно числу инверсий — в этом же и главный недостаток: за один обмен элемент сдвигается лишь на одну позицию. Практическая ценность нулевая, вставки делают ту же работу с втрое меньшей константой; держите пузырёк как иллюстрацию инвариантов, не более.

Сортировка вставками — рабочая лошадка всех гибридов

def insertion_sort(a: list, lo: int = 0, hi: int | None = None) -> list:
    """Сортирует полуинтервал a[lo:hi]. Устойчива, in-place."""
    hi = len(a) if hi is None else hi
    for i in range(lo + 1, hi):
        key = a[i]
        j = i - 1
        # сдвигаем вправо всё, что строго больше key
        while j >= lo and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key
    return a

Ключевой факт: время работы — Θ(n + I), где I — число инверсий. На отсортированном массиве внутренний цикл не выполняется ни разу (чистые O(n)); если каждый элемент отстоит от своего места не более чем на k позиций — O(nk).

Именно поэтому все промышленные сортировки переключаются на вставки для подмассивов длиной 16–32 элемента: там n² с крошечной константой, линейный доступ к памяти и предсказуемые ветвления бьют n log n с рекурсией и вызовами. Число 16–32 — не магия, а точка пересечения констант на типичном железе; в CPython minrun ≈ 32–64, в libstdc++ _S_threshold = 16. Отдельный нюанс: бинарные вставки (позиция ищется бинарным поиском) снижают число сравнений до O(n log n), но перемещений остаётся O(n²) — выигрыш есть, только когда сравнение дорогое, а перемещение дешёвое.

Сортировка выбором и сортировка Шелла

Выбором делает ровно n−1 обменов — минимально возможное число перемещений, и это её единственное достоинство (уместна, когда запись катастрофически дорога: EEPROM, сетевые перестановки). Устойчивой она не является: обмен «дальнего» минимума с текущей позицией перепрыгивает через равные элементы.

Сортировка Шелла — вставки с убывающим шагом (gap): при большом шаге элементы прыгают далеко и число инверсий падает быстро, а к моменту gap = 1 массив почти отсортирован и финальные вставки работают почти линейно. С последовательностью Седжвика даёт около O(n^{4/3}). Живёт там, где нельзя выделять память и нельзя допускать рекурсию — embedded и ядра ОС.

Сортировка слиянием: предсказуемость как фича

Классическое разделяй-и-властвуй: делим пополам, сортируем половины, сливаем.

def merge_sort(a: list) -> list:
    if len(a) > 1:
        _msort(a, a[:], 0, len(a))   # ОДИН буфер на весь запуск, а не на каждый уровень
    return a


def _msort(a: list, buf: list, lo: int, hi: int) -> None:
    if hi - lo <= 32:                # мелкие куски отдаём вставкам
        insertion_sort(a, lo, hi)
        return
    mid = (lo + hi) // 2
    _msort(a, buf, lo, mid)
    _msort(a, buf, mid, hi)
    if a[mid - 1] <= a[mid]:         # половины уже стыкуются — слияние не нужно
        return
    buf[lo:hi] = a[lo:hi]
    i, j = lo, mid
    for k in range(lo, hi):
        # <= вместо < — вот здесь и рождается устойчивость
        if i < mid and (j >= hi or buf[i] <= buf[j]):
            a[k], i = buf[i], i + 1
        else:
            a[k], j = buf[j], j + 1

Сложность. Рекуррента T(n) = 2T(n/2) + Θ(n) даёт Θ(n log n) по мастер-теореме — и это и лучший, и худший случай; память Θ(n). Отметьте две микрооптимизации в коде: единственный буфер (наивная реализация со срезами аллоцирует O(n log n) памяти суммарно) и проверка a[mid-1] <= a[mid], делающая алгоритм частично адаптивным почти бесплатно. Где merge sort незаменим: на связных списках (слияние переставляет указатели за O(1) доп. памяти, тогда как quicksort требует произвольного доступа — отсюда list_sort() в ядре Linux); во внешней сортировке, когда данные не влезают в память и куски сливаются k-путевым слиянием через кучу (см. Потоковые алгоритмы и внешняя память); там, где устойчивость требуется спецификацией; и в параллельных реализациях — две половины независимы, идеальный fork/join (параллельные алгоритмы). Существует и in-place merge за O(n log n) времени и O(1) памяти (алгоритм Кронрода, std::inplace_merge при нехватке буфера), но константа настолько велика, что выгоднее выделить буфер — хотя бы на n/2, скопировав только левую половину.

Быстрая сортировка: как не наступить на O(n²)

Quicksort выбирает опорный элемент, разбивает массив и рекурсивно сортирует части. Вся инженерия здесь — в разбиении и в выборе опорного.

Разбиение

Схема Ломуто проще, но делает больше обменов и катастрофически ведёт себя на массиве из одинаковых элементов: все элементы попадают в одну часть, глубина рекурсии n. Схема Хоара экономнее. Но настоящий ответ для данных с повторами — трёхпутевое разбиение (задача о голландском флаге Дейкстры):

def partition3(a: list, lo: int, hi: int, pivot) -> tuple[int, int]:
    """Переставляет a[lo..hi] так, что < pivot | == pivot | > pivot.
    Возвращает границы среднего блока."""
    lt, i, gt = lo, lo, hi
    while i <= gt:
        if a[i] < pivot:
            a[lt], a[i] = a[i], a[lt]
            lt += 1
            i += 1
        elif a[i] > pivot:
            a[i], a[gt] = a[gt], a[i]
            gt -= 1                  # i НЕ увеличиваем: пришедший справа элемент не проверен
        else:
            i += 1
    return lt, gt

Средний блок из равных элементов исключается из дальнейшей рекурсии. На массиве, где всего k различных значений, сортировка становится O(n log k); на массиве из одинаковых элементов — O(n).

Выбор опорного и защита от худшего случая

Худший случай O(n²) наступает, когда опорный систематически оказывается около края. Первый или последний элемент — худший выбор: на уже отсортированном входе (самый частый реальный паттерн!) получаем гарантированную деградацию. Инженерные решения:

• Медиана трёх (первый, средний, последний) — снимает проблему отсортированного входа. Для больших массивов — «ninther» Тьюки (медиана трёх медиан трёх), как в Bentley–McIlroy.
• Случайный опорный — переводит гарантию из «худшего входа» в «худшей удачи»: ожидание O(n log n) для любого фиксированного входа, вероятность деградации исчезающе мала. Подробный вероятностный анализ — в статье Рандомизированные алгоритмы. Важно: детерминированная медиана трёх уязвима к антагонистическому входу — существуют «killer»-массивы, специально сконструированные под конкретную реализацию, и это реальная DoS-поверхность.
• Introsort (Дэвид Массер, 1997): считаем глубину рекурсии; превысила 2⌊log₂ n⌋ — переключаемся на heapsort. Получаем среднюю скорость quicksort и жёсткую гарантию O(n log n). Это и есть std::sort в C++.

def intro_sort(a: list) -> list:
    if len(a) < 2:
        return a
    # предел глубины 2*floor(log2 n); bit_length() даёт floor(log2 n) + 1
    _intro(a, 0, len(a) - 1, depth=2 * (len(a).bit_length() - 1))
    return insertion_sort(a)         # один финальный проход по «почти отсортированному»


def _intro(a: list, lo: int, hi: int, depth: int) -> None:
    while hi - lo + 1 > 16:          # мелочь оставляем финальным вставкам
        if depth == 0:               # аварийный тормоз: heapsort на отрезке (см. ниже)
            heapsort_range(a, lo, hi)
            return
        depth -= 1
        # медиана трёх: сортирующая сеть из 3 сравнений, берём средний
        pivot = sorted((a[lo], a[lo + (hi - lo) // 2], a[hi]))[1]
        lt, gt = partition3(a, lo, hi, pivot)
        # рекурсия в МЕНЬШУЮ половину, итерация по большей => стек гарантированно O(log n)
        if lt - lo < hi - gt:
            _intro(a, lo, lt - 1, depth)
            lo = gt + 1
        else:
            _intro(a, gt + 1, hi, depth)
            hi = lt - 1

Приём «рекурсия в меньшую половину, цикл по большей» (tail-call elimination вручную) — обязательный: без него стек может вырасти до O(n) и уронить процесс раньше, чем закончится сортировка.

Почему quicksort быстрее merge sort при одинаковой асимптотике

Обе Θ(n log n), но quicksort работает на месте и с последовательным доступом к памяти: разбиение — это два линейных прохода, идеальных для аппаратного префетчера, тогда как merge sort постоянно читает из буфера и пишет в массив, удваивая трафик памяти. На современном железе разница в 1.5–3 раза не редкость; подробнее про кэш и предсказание ветвлений — в практической оптимизации.

Современное развитие темы — BlockQuicksort (Edelkamp & Weiß, 2016) и pdqsort (Orson Peters, 2016). Ключевая идея BlockQuicksort: непредсказуемая ветка if (a[i] < pivot) стоит десятки тактов на mispredict; заменим её на branchless-запись индексов в буфер смещений — и разбиение ускорится вдвое. pdqsort добавляет детекцию паттернов, защиту от плохих разбиений и переключение на heapsort. Именно pdqsort стоит сегодня в sort Go (с 1.19) и лежал в основе slice::sort_unstable в Rust.

Пирамидальная сортировка: гарантия без буфера

def heapsort(a: list) -> None:
    """O(n log n) в худшем случае, O(1) памяти, неустойчива.
    В introsort используется вариант с параметрами (lo, hi) — смещением базы."""
    n = len(a)
    for i in range(n // 2 - 1, -1, -1):       # построение кучи снизу вверх — O(n)
        _sift_down(a, i, n)
    for end in range(n - 1, 0, -1):
        a[0], a[end] = a[end], a[0]           # максимум уходит в конец
        _sift_down(a, 0, end)                 # восстанавливаем кучу на префиксе


def _sift_down(a: list, root: int, size: int) -> None:
    while (child := 2 * root + 1) < size:
        if child + 1 < size and a[child] < a[child + 1]:
            child += 1                        # берём большего из детей
        if a[root] >= a[child]:
            return
        a[root], a[child] = a[child], a[root]
        root = child

Heapsort — единственный из «большой тройки», кто даёт O(n log n) в худшем случае при O(1) памяти. Почему же он не победил? Из-за доступа к памяти: sift_down прыгает по индексам i → 2i+1 → 4i+3, и на больших массивах каждый шаг — промах кэша; плюс две плохо предсказуемые ветки на итерацию. На практике heapsort в 2–3 раза медленнее quicksort и живёт как «аварийный тормоз» в introsort и как способ сортировать в жёстко ограниченной памяти (real-time, ядро, embedded). Отдельно стоит помнить: построение кучи — O(n), а не O(n log n), что делает её идеальной для «top-k из n» за O(n log k). Про сами кучи — в треке Структуры данных.

Timsort: что на самом деле делает list.sort()

Тим Петерс написал Timsort для CPython в 2002 году, исходя из наблюдения: реальные данные состоят из отсортированных кусков. Timsort ищет такие куски (runs), при необходимости достраивает их вставками и сливает по правилам, которые поддерживают сбалансированность.

Механика по шагам

1. Поиск run. Идём слева направо, пока порядок не нарушится. Если участок строго убывающий — разворачиваем его на месте.

def count_run(a: list, lo: int, hi: int) -> int:
    """Длина максимального упорядоченного участка с позиции lo (полуинтервал [lo, hi))."""
    if hi - lo == 1:
        return 1
    i = lo + 1
    if a[i] < a[lo]:
        # СТРОГО убывающий: условие a[i+1] < a[i], а не <=.
        # Разворот участка с равными элементами убил бы устойчивость.
        while i + 1 < hi and a[i + 1] < a[i]:
            i += 1
        a[lo:i + 1] = a[lo:i + 1][::-1]
    else:
        while i + 1 < hi and a[i + 1] >= a[i]:
            i += 1
    return i - lo + 1

Обратите внимание на асимметрию < и >=: она и есть причина устойчивости Timsort. Это классический пример того, как одна строгость знака в условии — часть доказательства корректности.

2. Выбор minrun. Короткие runs достраиваются бинарными вставками до длины minrun (32–64). Значение вычисляется так: берутся старшие 6 бит n, и если хоть один отброшенный бит был единицей — результат увеличивается на 1 (r |= n & 1 в цикле сдвигов). Смысл — сделать n / minrun близким к степени двойки, тогда дерево слияний получается сбалансированным, без одного «огрызка» в конце.

3. Стек runs и инварианты. Runs кладутся в стек, и после каждого push проверяются условия на длины трёх верхних (X, Y, Z сверху вниз): Z > Y + X и Y > X. Если нарушено — сливаются два соседних run (тот из X/Z, что меньше, объединяется с Y). Инварианты гарантируют, что длины runs растут экспоненциально (как числа Фибоначчи), а значит глубина стека — O(log n), и сливаются куски примерно равного размера.

4. Galloping mode. При слиянии двух runs, если из одного подряд взято MIN_GALLOP (=7) элементов, Timsort переключается в «галоп»: вместо поэлементного сравнения он бинарным поиском ищет, сколько элементов из этого run можно взять сразу. На данных вроде [1..1000] + [2000..3000] слияние вырождается в два бинарных поиска и два memcpy — O(log n) сравнений вместо O(n).

Знаменитый баг

В 2015 году группа исследователей (de Gouw, Rot, de Boer, Bubel, Hähnle) при попытке формально верифицировать java.util.Collections.sort обнаружила, что инварианты стека проверялись недостаточно глубоко, а размер стека был рассчитан из неверной оценки. На специально сконструированном входе (порядка 67 миллионов элементов) Java бросала ArrayIndexOutOfBoundsException; тот же дефект жил в CPython, Android и Rust. Разбор — в статье «OpenJDK’s java.util.Collections.sort() is broken». Мораль не «Timsort плох», а обратная: алгоритм, написанный экспертом и прошедший миллиарды запусков в трёх экосистемах, содержал ошибку, которую нашла только машинная верификация. Инварианты нужно не только формулировать, но и доказывать.

Powersort: что в CPython сегодня

Начиная с версии 3.11 CPython заменил эвристику слияния Timsort на powersort (Мунро и Вильд, «Nearly-Optimal Mergesorts», arXiv:1805.04154). Идея: политику слияния можно свести к построению почти-оптимального бинарного дерева слияний по длинам runs — как в кодах Хаффмана. Powersort даёт формальную гарантию близости к энтропийному оптимуму и при этом проще инвариантов Тима; поиск runs, galloping и minrun остались прежними, сменилось только правило «когда сливать». Канонический источник — listsort.txt в репозитории CPython: редкий случай, когда комментарий к коду читается как хорошая статья.

Сортировки без сравнений: пробить n log n

Теорема о нижней границе говорит о сравнениях. Если ключ — целое число ограниченной ширины, мы можем использовать его как индекс, и линейное время становится доступным.

Counting sort

def counting_sort(a: list, key, k: int) -> list:
    """Устойчивая сортировка по целому ключу из диапазона [0, k]. O(n + k)."""
    cnt = [0] * (k + 1)
    for x in a:
        cnt[key(x)] += 1
    total = 0
    for v in range(k + 1):               # эксклюзивные префиксные суммы = стартовые позиции
        cnt[v], total = total, total + cnt[v]
    out = [None] * len(a)
    for x in a:                          # проход СЛЕВА НАПРАВО даёт устойчивость
        pos = key(x)
        out[cnt[pos]] = x
        cnt[pos] += 1
    return out

Условие применимости: k = O(n). Сортировать миллион 32-битных чисел через counting sort — это 4 миллиарда счётчиков, то есть нет. А вот отсортировать 10 миллионов записей по полю «возраст» (k = 120) или «код страны» (k = 999) — идеальный кейс, один проход и никаких сравнений.

Поразрядная сортировка (radix)

Разбиваем ключ на d разрядов по b бит и применяем counting sort к каждому разряду, начиная с младшего (LSD). Устойчивость каждого прохода — не деталь реализации, а условие корректности: она сохраняет порядок, установленный предыдущими разрядами.

def radix_sort_u64(a: list[int], bits: int = 64, radix_bits: int = 8) -> list[int]:
    """LSD radix для неотрицательных целых. O((bits/radix_bits) * (n + 2^radix_bits))."""
    if len(a) < 2:
        return a
    base = 1 << radix_bits
    mask = base - 1
    buf = [0] * len(a)
    for shift in range(0, bits, radix_bits):
        cnt = [0] * base
        for x in a:
            cnt[(x >> shift) & mask] += 1
        # если весь массив попал в одну корзину — разряд неинформативен, пропускаем проход
        if cnt[(a[0] >> shift) & mask] == len(a):
            continue
        total = 0
        for v in range(base):
            cnt[v], total = total, total + cnt[v]
        for x in a:
            d = (x >> shift) & mask
            buf[cnt[d]] = x
            cnt[d] += 1
        a[:] = buf
    return a

Сложность. O(d·(n + 2^b)) времени, O(n + 2^b) памяти. Для 64-битных ключей и b = 8 это 8 проходов — то есть O(8n). Сравнительная сортировка того же массива на n = 10⁸ потратит log₂ n ≈ 27 уровней. Radix выигрывает, и заметно.

Подводные камни, на которых спотыкаются все:

• Отрицательные числа. Знаковый бит ломает порядок: -1 в дополнительном коде — это 0xFFFF..., то есть «самое большое». Решение — на последнем (знаковом) проходе инвертировать порядок корзин, либо перед сортировкой прибавить смещение (XOR со старшим битом).
• Числа с плавающей точкой. IEEE-754 почти монотонен в битовом представлении, но не совсем: у отрицательных порядок обратный. Стандартный трюк — преобразование ключа:

import struct


def float_to_sortable_u64(x: float) -> int:
    """Монотонное отображение double -> uint64: битовый порядок совпадает с числовым."""
    bits = struct.unpack('<Q', struct.pack('<d', x))[0]
    if bits >> 63:                        # отрицательное: инвертируем все биты
        return bits ^ 0xFFFFFFFFFFFFFFFF
    return bits ^ 0x8000000000000000      # положительное: поднимаем знаковый бит

• Строки переменной длины. LSD требует одинаковой длины ключа. Для строк применяют MSD-radix с рекурсией по корзинам (по сути — trie-обход) и переключением на вставки для мелких корзин. Это тема статьи Строковые алгоритмы.
• Кэш. Наивный LSD с b = 8 пишет в 256 разных мест массива — это 256 «потоков записи» и постоянные конфликты в TLB. Промышленные реализации (например, ska_sort Мальте Скарупке) используют программную буферизацию по корзинам и адаптивный выбор основания.

Рядом стоит bucket sort: если ключи распределены равномерно на отрезке, раскидываем их по n корзинам по значению, сортируем каждую вставками и конкатенируем — ожидаемое O(n), худшее O(n²) (все в одну корзину). Это редкий случай, когда алгоритм опирается на предположение о распределении входа, а не только о его размере, и потому в проде требует контроля: перекос данных мгновенно превращает его в квадрат.

Как выбирать: практический алгоритм принятия решения

Что стоит за узлом «берите встроенную» в конкретных экосистемах:

Типичные ошибки

1. Компаратор, нарушающий строгий слабый порядок. Самая частая и самая коварная. Компаратор обязан быть иррефлексивным (cmp(x, x) = false), антисимметричным и транзитивным — включая транзитивность несравнимости. Классический баг:

# ПЛОХО: переполнение (в C/Java) и ложь при равенстве по вторичному признаку
cmp = lambda x, y: x.score - y.score

# ПЛОХО: не транзитивно, если tolerance > 0
cmp = lambda x, y: 0 if abs(x - y) < 1e-9 else (-1 if x < y else 1)

Второй пример смертелен: a ≈ b, b ≈ c, но a < c. Timsort в Java при обнаружении такого компаратора бросает IllegalArgumentException: Comparison method violates its general contract! — и это не ошибка сортировки, а диагностика вашего компаратора. В C++ UB: std::sort может выйти за границы массива.

2. Нестабильный ключ: NaN и мутации. NaN не сравним ни с чем (любое сравнение — false) и разрушает порядок в любой сортировке на сравнениях: отфильтруйте его или используйте тотальный порядок (в Rust — total_cmp). Та же категория — компаратор, читающий изменяемое поле, которое параллельно меняет другой поток: порядок «плывёт», результат непредсказуем, иногда падение.

3. Дорогой компаратор вместо ключа. items.sort(key=cmp_to_key(...)) с тяжёлым вычислением внутри вызывает его O(n log n) раз; items.sort(key=expensive) — ровно n раз. Идиома key= в Python и есть decorate-sort-undecorate: ключи считаются один раз и сортируются вместе с элементами.

4. Ставка на устойчивость там, где её нет. Arrays.sort для примитивов в Java неустойчива, std::sort неустойчива, sort.Slice в Go неустойчива. Многоключевая сортировка последовательными проходами на них молча даёт неверный результат — и не воспроизводится на маленьких тестах, потому что многие реализации переключаются на устойчивые вставки при n < 16.

5. Сортировка вместо частичной выборки. «Топ-10 из миллиона» — не задача сортировки. heapq.nlargest / std::partial_sort / nth_element дают O(n log k) или O(n) против O(n log n). Алгоритм Quickselect (тот же partition, но рекурсия только в одну сторону) находит k-ю порядковую статистику за ожидаемые O(n).

6. Сортировка в цикле. Пересортировка коллекции после каждой вставки — O(n² log n). Нужна структура с упорядоченностью: куча, сбалансированное дерево, SortedList.

Эволюция: как мы сюда пришли

Сюжет читается ясно: сначала боролись за асимптотику (до 1964 года), потом за константу и гарантии (1993–1997), затем за адаптивность к реальным данным (2002+), а последнее десятилетие — за согласие с микроархитектурой процессора: предсказание ветвлений, кэш, SIMD. Асимптотика не менялась с 1964 года; практическая скорость выросла в разы.

Мини-итог

• Нижняя граница Ω(n log n) для сравнений доказывается деревом решений за пять строк: merge sort и heapsort асимптотически неулучшаемы. Выбирают же сортировку не по асимптотике, а по четырём осям: устойчивость, память, адаптивность, стоимость сравнения против стоимости перемещения.
• Insertion sort — не игрушка, а обязательный базовый блок каждого промышленного гибрида на подмассивах до ~32 элементов.
• Quicksort быстрее merge sort из-за работы на месте и последовательного доступа к памяти; вся его инженерия — в выборе опорного (медиана трёх / случайность) и в трёхпутевом разбиении для повторов; introsort добавляет гарантию.
• Timsort выигрывает, потому что реальные данные состоят из runs; устойчивость держится на строгости знака при развороте убывающих участков, сбалансированность — на инвариантах стека.
• Counting и radix обходят нижнюю границу, работая с ключом как с индексом; цена — ограничения на тип ключа, память под корзины и аккуратность со знаком и float.
• В проде почти всегда правильный ответ — встроенная сортировка. Писать свою стоит, лишь когда вы точно знаете, какое именно её свойство вам не подходит.

Источники

• T. Cormen, C. Leiserson, R. Rivest, C. Stein. Introduction to Algorithms, 4-е издание — главы 2, 6, 7, 8. mitpress.mit.edu/9780262046305
• R. Sedgewick, K. Wayne. Algorithms, 4-е издание, глава 2 + визуализации: algs4.cs.princeton.edu/20sorting
• D. Knuth. The Art of Computer Programming, том 3: Sorting and Searching — исчерпывающий справочник.
• T. Peters. listsort.txt — описание Timsort от автора: github.com/python/cpython/blob/main/Objects/listsort.txt; S. de Gouw и др. OpenJDK’s java.util.Collections.sort() is broken: envisage-project.eu
• J. Munro, S. Wild. Nearly-Optimal Mergesorts (powersort): arxiv.org/abs/1805.04154
• S. Edelkamp, A. Weiß. BlockQuicksort: arxiv.org/abs/1604.06697; O. Peters. pdqsort: github.com/orlp/pdqsort
• J. Bentley, M. D. McIlroy. Engineering a Sort Function, Software: Practice and Experience, 1993 — doi.org/10.1002/spe.4380231105
• M. Skarupke. I Wrote a Faster Sorting Algorithm (ska_sort, инженерия radix): probablydance.com
• Бенчмарки и тесты корректности современных реализаций (Rust ipnsort/driftsort): github.com/Voultapher/sort-research-rs
• Документация: docs.python.org — Sorting HOW TO, pkg.go.dev/sort, en.cppreference.com/w/cpp/algorithm/sort

Что дальше

Отсортированный массив сам по себе редко является целью — он нужен, чтобы искать быстро. В следующей статье разберём, как из упорядоченности выжать логарифм: Поиск и бинарный поиск, в том числе по ответу — включая классические ошибки с границами, поиск по вещественному ответу и мощнейший приём «бинарный поиск по ответу», который превращает задачу оптимизации в задачу проверки предиката.