Что на самом деле стоит в стандартных библиотеках

Если ты знаешь, что Timsort - это адаптивное устойчивое слияние с поиском runs и вставками, а introsort - быстрая сортировка с переключением на пирамидальную и вставки, и понимаешь, почему библиотеки выбрали именно гибриды, листай до «Теперь сам».

Как думаешь, какую из изученных сортировок поставили в стандартную библиотеку

Соблазн ответить «быструю - она же самая быстрая». Но мы видели её слабости: худший случай Θ(n²), риск переполнить стек, неустойчивость. У слияния своя беда - лишняя память; у пирамидальной - плохая локальность. Ни одна «чистая» сортировка не идеальна. Поэтому в библиотеках стоят не они, а ГИБРИДЫ - алгоритмы, собранные из нескольких изученных, где сильная сторона одного закрывает слабость другого. Разберём два самых важных: Timsort и introsort.

На что это похоже

Хороший мастер не работает одним инструментом. Он берёт дрель для отверстий, отвёртку для винтов, молоток для гвоздей - и переключается по ходу дела. Библиотечная сортировка устроена так же: «а вот тут кусок уже почти упорядочен - досортирую вставками; тут большой случайный массив - поделю и сольют; а если разбиение вдруг пошло плохо и грозит квадратом - переключусь на надёжную пирамидальную». Один инструмент под каждую ситуацию, всё внутри одной функции сортировки.

Механизм: два главных гибрида

Timsort (Python, Java для объектов; автор Тим Петерс). Идея - реальные данные часто частично упорядочены, и это надо использовать:

1. Проходит массив и находит runs - уже упорядоченные подряд куски (возрастающие или убывающие; убывающие переворачивает).
2. Слишком короткие runs удлиняет, досортировывая соседние элементы ВСТАВКАМИ (адаптивно, дёшево на почти готовом).
3. СЛИВАЕТ runs между собой (как в сортировке слиянием), по хитрым правилам баланса.

Итог: устойчив, гарантированно Θ(n·log n) в худшем случае, а на почти упорядоченных данных - близко к Θ(n). Цена - Θ(n) памяти (как у слияния).

Introsort (C++ std::sort и родственники; «introspective sort»). Идея - взять быструю сортировку, но подстраховать её от худшего случая:

1. Сортирует БЫСТРОЙ сортировкой (с хорошим выбором опорного).
2. СЛЕДИТ за глубиной рекурсии; если она превысила ~2·log n (признак, что опорные делят плохо и дело пахнет Θ(n²)) - переключается на ПИРАМИДАЛЬНУЮ сортировку для этого куска (она гарантирует n·log n).
3. Маленькие подмассивы (≤ ~16 элементов) добивает ВСТАВКАМИ.

Итог: средняя скорость быстрой сортировки, гарантия Θ(n·log n) в худшем случае, работа на месте. Цена - неустойчивость (наследство быстрой).

Правило

Стандартные библиотеки используют ГИБРИДЫ. Timsort (объекты в Python/Java) - адаптивное УСТОЙЧИВОЕ слияние: ищет упорядоченные куски (runs), короткие добивает вставками, сливает; Θ(n·log n) в худшем, Θ(n) на почти упорядоченных, ест Θ(n) памяти. Introsort (числа в C++) - БЫСТРАЯ сортировка с переключением на пирамидальную при глубокой рекурсии и вставками на маленьких кусках: Θ(n·log n) гарантированно, на месте, НЕ устойчив. Каждый гибрид закрывает слабости своих составных частей.

Разбор: почему Python-объекты - Timsort, а C++-числа - introsort

Выбор не случаен и отражает приоритеты. Для сортировки ОБЪЕКТОВ (Python sorted, Java Arrays.sort для Object[]) важна УСТОЙЧИВОСТЬ - чтобы работала многоключевая сортировка из прошлого урока, - и хорошая работа на реальных, часто почти упорядоченных данных. Timsort даёт и то, и другое, а расход Θ(n) памяти приемлем. Для сортировки ПРИМИТИВОВ (C++ std::sort, Java Arrays.sort для int[]) устойчивость не нужна вовсе (два равных числа неразличимы - переставляй как хочешь), зато ценна работа НА МЕСТЕ и максимальная скорость - поэтому берут вариант быстрой сортировки со страховкой (в C++ это introsort, в Java для примитивов - двухопорная быстрая сортировка с теми же приёмами: вставки на мелких кусках, защита от худшего случая). Один язык может использовать ОБА: Java сортирует объекты Timsort'ом (нужна устойчивость), а примитивы - быстрой сортировкой (устойчивость не нужна, память дорога).

Разбор: как гибриды собраны из наших глав

Ничего нового в этих гибридах нет - только комбинация того, что мы уже разобрали. Timsort = слияние (глава 2) + вставки (глава 1) + адаптивность (глава 1). Introsort = быстрая (глава 2) + пирамидальная (глава 3) + вставки (глава 1). Переключение на вставки для маленьких кусков есть в обоих - потому что у вставок крохотные накладные расходы, и на десятке элементов они бьют любую n·log n (её рекурсия и служебные действия на коротышах не окупаются). Переключение introsort на пирамидальную - это прямое применение её уникального свойства из главы 3: гарантия n·log n НА МЕСТЕ, идеальная страховка. То есть всё, что ты изучил, реально стоит в проме - просто собрано вместе.

Что ломается без этого

Первая ошибка - написать свою «быструю сортировку» и поставить в прод вместо встроенной: почти наверняка получишь худший случай Θ(n²) на реальных (часто упорядоченных) данных и, возможно, переполнение стека - всё то, от чего introsort и Timsort специально защищены. Встроенная сортировка почти всегда лучше самописной. Вторая ошибка - считать, что «быстрая сортировка = то, что в библиотеке»: там гибрид, и он устойчивее (в обоих смыслах) учебной быстрой. Третья - удивляться, почему sorted в Python устойчив, а std::sort в C++ нет: это осознанный выбор под тип данных (объекты против примитивов).

Зачем это в работе

Практический вывод короткий: пользуйся встроенной сортировкой, она уже гибрид и уже учла всё, что мы разбирали. Знание, ЧТО именно там стоит, помогает в двух вещах. Первое - предсказывать поведение: sorted в Python устойчив и быстр на почти упорядоченных данных (это Timsort), поэтому многоключевая сортировка и работа с почти готовыми данными дёшевы. Второе - на собеседовании и в спорах: «какая сортировка в стандартной библиотеке?» - правильный ответ не «быстрая», а «гибрид: Timsort для объектов, introsort/быстрая для примитивов», и ты можешь объяснить, почему именно так. Это и отличает того, кто изучил сортировки, от того, кто заучил три названия.

Теперь сам

Почему и Timsort, и introsort на маленьких подмассивах переключаются именно на сортировку ВСТАВКАМИ, а не продолжают своим основным методом?