Сортировки

TL;DR

Сортировка — упорядочивание элементов по ключу. Все сравнительные сортировки (использующие только сравнения) подчиняются нижней границе [math]\displaystyle{ \Omega(n\log n) }[/math]: дерево решений содержит [math]\displaystyle{ n! }[/math] исходов-перестановок, значит глубина [math]\displaystyle{ \ge \log_2(n!) = \Theta(n\log n) }[/math]. Быстрее [math]\displaystyle{ n\log n }[/math] удаётся только не-сравнительным сортировкам — подсчётом ([math]\displaystyle{ O(n+k) }[/math]), поразрядно ([math]\displaystyle{ O(d(n+k)) }[/math]), карманной (среднее [math]\displaystyle{ O(n) }[/math]) — за счёт использования структуры ключей. Внутри класса [math]\displaystyle{ O(n\log n) }[/math] выбор определяется свойствами: устойчивость (слияние, Timsort), память [math]\displaystyle{ O(1) }[/math] (Пирамидальная сортировка), средняя скорость (Быстрая сортировка, introsort). Эта статья — обзор; детали каждого алгоритма — в отдельных статьях: Быстрая сортировка, Сортировка слиянием, Пирамидальная сортировка, Timsort.

Свойство	Значение
Класс	Алгоритмы упорядочивания по ключу
Сравнительные	нижняя граница [math]\displaystyle{ \Omega(n\log n) }[/math]
Достижимо	[math]\displaystyle{ \Theta(n\log n) }[/math] в худшем: слияние, heapsort, Timsort
Быстрее	только не-сравнительные: подсчёт, radix, bucket ([math]\displaystyle{ O(n) }[/math]/[math]\displaystyle{ O(n+k) }[/math])
Свойства	устойчивость, in-place, адаптивность, гарантия
Библиотеки	`std::sort` (introsort), `std::stable_sort`, Python/Java (Timsort)
Обозначения	[math]\displaystyle{ n }[/math] — число элементов, [math]\displaystyle{ k }[/math] — диапазон ключей, [math]\displaystyle{ d }[/math] — число разрядов
Связанные	Асимптотическая сложность, Амортизационный анализ

Определения

Задача сортировки. Дан массив [math]\displaystyle{ a[1..n] }[/math] с ключами из линейно упорядоченного множества; требуется переставить элементы так, чтобы ключи не убывали: [math]\displaystyle{ a[1] \le a[2] \le \dots \le a[n] }[/math].

Сравнительная сортировка (comparison sort) — алгоритм, который получает информацию о ключах только через сравнения [math]\displaystyle{ a[i] \lessgtr a[j] }[/math]. К этому классу относятся quicksort, mergesort, heapsort, insertion sort и др.

Не-сравнительная сортировка — использует дополнительную структуру ключей (диапазон, разряды, распределение) и не считает сравнения как основную операцию: counting sort, radix sort, bucket sort.

Устойчивость (stability) — равные ключи сохраняют исходный взаимный порядок.

На месте (in-place) — алгоритм переставляет элементы в самом массиве, используя [math]\displaystyle{ O(1) }[/math] (или [math]\displaystyle{ O(\log n) }[/math] под рекурсию) памяти сверх входа.

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

Дерево решений (decision tree) — модель сравнительной сортировки: каждый внутренний узел — сравнение, каждый лист — результат (перестановка); высота дерева равна числу сравнений в худшем случае.

Нижняя граница [math]\displaystyle{ \Omega(n\log n) }[/math]. Любая сравнительная сортировка выполняет не менее [math]\displaystyle{ \lceil\log_2(n!)\rceil = \Theta(n\log n) }[/math] сравнений в худшем случае.

Обозначения. [math]\displaystyle{ n }[/math] — число элементов; [math]\displaystyle{ k }[/math] — число возможных значений ключа; [math]\displaystyle{ d }[/math] — число разрядов; [math]\displaystyle{ \log }[/math] — двоичный.

Мотивация и интуиция

Сортировка — базовая операция: она ускоряет поиск (Дерево Фенвика, двоичный поиск), объединение (join в СУБД), отображение и дедупликацию. Вопрос «как быстро в принципе?» имеет точный ответ: сравнительные сортировки не могут быть быстрее [math]\displaystyle{ n\log n }[/math], и этот предел достигается (mergesort, heapsort). См. рис. 1 и рис. 2.

Рис. 1. Два семейства: сравнительные (граница [math]\displaystyle{ n\log n }[/math]) и не-сравнительные (используют структуру ключей).

Ключевая идея нижней границы — подсчёт различимых исходов. Чтобы отсортировать [math]\displaystyle{ n }[/math] различных элементов, алгоритм должен уметь отличить любую из [math]\displaystyle{ n! }[/math] перестановок. Каждое сравнение даёт один бит информации (две ветви), поэтому дерево решений глубины [math]\displaystyle{ d }[/math] имеет не более [math]\displaystyle{ 2^d }[/math] листьев. Отсюда [math]\displaystyle{ 2^d \ge n! }[/math], то есть [math]\displaystyle{ d \ge \log_2(n!) = \Theta(n\log n) }[/math].

Обойти границу можно, выйдя за модель сравнений: если ключи — целые в диапазоне [math]\displaystyle{ 0..k }[/math], можно посчитать их частоты и разложить элементы без сравнений (counting sort); если ключи — мультиразрядные, сортировать по разрядам (radix); если равномерны — раскладывать по карманам (bucket).

Рис. 2. Для [math]\displaystyle{ n = 3 }[/math]: 6 листьев-перестановок; отсюда [math]\displaystyle{ \ge \log_2 6 \approx 2.58 }[/math], то есть [math]\displaystyle{ \ge 3 }[/math] сравнения.

Устройство

Сравнительные сортировки делятся на три группы по времени (см. рис. 1):

[math]\displaystyle{ \Theta(n^2) }[/math]: вставками, выбором, пузырьком — простые, хороши на малых [math]\displaystyle{ n }[/math];
[math]\displaystyle{ \Theta(n\log n) }[/math]: слиянием (устойчива, [math]\displaystyle{ O(n) }[/math] памяти), heapsort ([math]\displaystyle{ O(1) }[/math] памяти), Timsort (устойчива, адаптивна);
быстрая: [math]\displaystyle{ O(n\log n) }[/math] в среднем, [math]\displaystyle{ \Theta(n^2) }[/math] в худшем (сводится к [math]\displaystyle{ O(n\log n) }[/math] в introsort).

Нижняя граница: доказательство (см. рис. 3)

Модель. Сортирующий алгоритм — это дерево решений: в каждом узле — сравнение двух элементов, две ветви соответствуют исходам. Листья — возможные результаты.

Доказательство. Для [math]\displaystyle{ n }[/math] различных ключей существует [math]\displaystyle{ n! }[/math] перестановок, и алгоритм обязан различать их (разным входам, требующим разного порядка, соответствуют разные листья). Двоичное дерево высоты [math]\displaystyle{ d }[/math] имеет не более [math]\displaystyle{ 2^d }[/math] листьев, поэтому [math]\displaystyle{ 2^d \ge n! }[/math], откуда [math]\displaystyle{ d \ge \log_2(n!) }[/math]. По формуле Стирлинга [math]\displaystyle{ n! \approx \sqrt{2\pi n}(n/e)^n }[/math], значит [math]\displaystyle{ \log_2(n!) = n\log_2 n - 1.44n + O(\log n) = \Theta(n\log n) }[/math]. [math]\displaystyle{ \square }[/math]

Следствие. Любой алгоритм из класса сравнений требует [math]\displaystyle{ \Omega(n\log n) }[/math] сравнений в худшем случае; algorithms слияния и heapsort достигают этой границы по порядку.

Рис. 3. [math]\displaystyle{ \log_2(n!) = \Theta(n\log n) }[/math]: верхняя и нижняя оценки зажимают границу.

Как обойти границу (см. рис. 4)

Отказавшись от сравнений, получаем линейные (по [math]\displaystyle{ n }[/math]) сортировки при подходящих ключах:

Counting sort: ключи [math]\displaystyle{ 0..k }[/math]; считаем частоты, строим префиксные суммы, раскладываем элементы на свои места. [math]\displaystyle{ O(n + k) }[/math].
Radix sort (LSD): сортируем устойчиво по младшему разряду, затем по следующему. [math]\displaystyle{ O(d(n+k)) }[/math], где [math]\displaystyle{ d }[/math] — число разрядов.
Bucket sort: равномерные ключи на [math]\displaystyle{ [0,1) }[/math]; раскладываем по карманам, каждый сортируем вставками. Среднее [math]\displaystyle{ O(n) }[/math].

Рис. 4. Подсчётом, поразрядно и карманами — ценой предположений о ключах.

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

Операции и алгоритмы

Группа: квадратичные сортировки

Вставками. На каждом шаге вставляем a[i] в отсортированный префикс, сдвигая большие элементы. [math]\displaystyle{ O(n^2) }[/math] (в худшем), [math]\displaystyle{ O(n) }[/math] на почти отсортированных; устойчива, in-place. Хороша на малых [math]\displaystyle{ n }[/math] и как «хвост» гибридов.

Выбором. Находим минимум в остатке и ставим на место. [math]\displaystyle{ O(n^2) }[/math], мало обменов ([math]\displaystyle{ O(n) }[/math]), но неустойчива и не адаптивна.

Пузырьком. Обмены соседних «неправильных» пар. [math]\displaystyle{ O(n^2) }[/math]; учебный, на практике заменяется вставками.

Группа: $O(n\log n)$

Слиянием (Сортировка слиянием): деление пополам и устойчивое слияние; гарантия [math]\displaystyle{ O(n\log n) }[/math], память [math]\displaystyle{ O(n) }[/math]; на списках — [math]\displaystyle{ O(\log n) }[/math].
Пирамидальная (Пирамидальная сортировка): max-куча и извлечение максимума; [math]\displaystyle{ O(n\log n) }[/math] всегда при [math]\displaystyle{ O(1) }[/math] памяти; неустойчива.
Быстрая (Быстрая сортировка): разбиение вокруг опорного; [math]\displaystyle{ O(n\log n) }[/math] в среднем, [math]\displaystyle{ \Theta(n^2) }[/math] в худшем; in-place, но неустойчива; introsort гарантирует [math]\displaystyle{ O(n\log n) }[/math].
Timsort (Timsort): natural runs + слияние с инвариантом стека; лучший [math]\displaystyle{ O(n) }[/math], худший [math]\displaystyle{ O(n\log n) }[/math]; устойчива и адаптивна.

Группа: не-сравнительные

Counting sort (см. рис. 4):

Алгоритм Counting-Sort(a, k)
Вход:  a[0..n−1], ключи — целые 0..k
Выход: a отсортирован (устойчиво)
Сложность: O(n + k) времени, O(n + k) памяти

1  for v ← 0 to k: cnt[v] ← 0
2  for i ← 0 to n − 1: cnt[a[i]] ← cnt[a[i]] + 1
3  for v ← 1 to k: cnt[v] ← cnt[v] + cnt[v − 1]      # префиксные суммы
4  for i ← n − 1 downto 0                              # справа налево → устойчиво
5      cnt[a[i]] ← cnt[a[i]] − 1
6      out[cnt[a[i]]] ← a[i]
7  return out

Radix sort (LSD): для каждого разряда (от младшего) выполнить устойчивую counting-сортировку по этому разряду. Корректность — индукция по разрядам: устойчивость сохраняет предыдущий порядок.

Bucket sort: разложить по [math]\displaystyle{ k }[/math] карманам по значению ключа, отсортировать карманы вставками (средний размер [math]\displaystyle{ O(1) }[/math] при равномерности), собрать. Среднее [math]\displaystyle{ O(n) }[/math], худший [math]\displaystyle{ O(n^2) }[/math].

Сводная таблица сложности

Алгоритм	Средний	Худший	Память	Устойчив	In-place	Адаптивен
Вставками	[math]\displaystyle{ O(n^2) }[/math]	[math]\displaystyle{ O(n^2) }[/math]	[math]\displaystyle{ O(1) }[/math]	да	да	да (O(n))
Выбором	[math]\displaystyle{ O(n^2) }[/math]	[math]\displaystyle{ O(n^2) }[/math]	[math]\displaystyle{ O(1) }[/math]	нет	да	нет
Слиянием	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(n) }[/math]	да	нет	слабо
Пирамидальная	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(1) }[/math]	нет	да	слабо
Быстрая	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(n^2) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	нет	да	слабо
Timsort	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(n) }[/math]	да	нет	да (O(n))
Подсчётом	[math]\displaystyle{ O(n+k) }[/math]	[math]\displaystyle{ O(n+k) }[/math]	[math]\displaystyle{ O(n+k) }[/math]	да	нет	нет
Radix (LSD)	[math]\displaystyle{ O(d(n+k)) }[/math]	[math]\displaystyle{ O(d(n+k)) }[/math]	[math]\displaystyle{ O(n+k) }[/math]	да	нет	нет
Bucket	[math]\displaystyle{ O(n) }[/math]	[math]\displaystyle{ O(n^2) }[/math]	[math]\displaystyle{ O(n) }[/math]	да*	нет	нет

Оговорки: *bucket sort устойчив, если карманы сортируются устойчиво и собираются по порядку. Не-сравнительные сортировки требуют предположений о ключах. Полная таблица — на рис. 5.

Трассировка примера

Замерим число сравнений на массиве из [math]\displaystyle{ n = 4096 }[/math] случайных чисел (прогон из «Служебного»):

Алгоритм	Сравнений (≈)	Отношение к [math]\displaystyle{ n\log_2 n }[/math]
Вставками	[math]\displaystyle{ \approx n^2/4 }[/math]	[math]\displaystyle{ \approx 21.5 }[/math]
Слиянием	[math]\displaystyle{ \approx 0.98\,n\log_2 n }[/math]	[math]\displaystyle{ \approx 1.0 }[/math]
Пирамидальная	[math]\displaystyle{ \approx 1.9\,n\log_2 n }[/math]	[math]\displaystyle{ \approx 1.9 }[/math]
Быстрая (медиана трёх)	[math]\displaystyle{ \approx 1.0\,n\log_2 n }[/math]	[math]\displaystyle{ \approx 1.0 }[/math]
Подсчётом	[math]\displaystyle{ 0 }[/math] сравнений	—

Все сравнительные не опускаются ниже [math]\displaystyle{ \log_2(n!) \approx n\log_2 n - 1.44n }[/math] — нижняя граница выполняется. Counting sort делает ноль сравнений элементов (использует ключи как индексы). Трассировка сверена с реализацией из раздела «Служебное».

Корректность и оценка сложности

Нижняя граница

Доказана выше через дерево решений: [math]\displaystyle{ d \ge \log_2(n!) = \Theta(n\log n) }[/math]. Более точная оценка с константами: [math]\displaystyle{ \log_2(n!) = n\log_2 n - 1.44n + O(\log n) }[/math].

Достижимость

Сортировка слиянием делает [math]\displaystyle{ T(n) = 2T(n/2) + \Theta(n) = \Theta(n\log n) }[/math] сравнений (см. Сортировка слиянием); heapsort — не более [math]\displaystyle{ 2n\log_2 n }[/math]; Timsort сохраняет [math]\displaystyle{ O(n\log n) }[/math]. Значит, граница достижима по порядку, и класс [math]\displaystyle{ O(n\log n) }[/math] для сравнений оптимален.

Корректность counting sort

После шага 3 cnt[v] — число элементов [math]\displaystyle{ \le v }[/math]. Проход справа налево (шаг 4) кладёт элемент на позицию cnt[a[i]] - 1, уменьшая счётчик: равные элементы идут в порядке справа налево, то есть устойчиво. После всех [math]\displaystyle{ n }[/math] шагов каждый элемент на своём месте. [math]\displaystyle{ \square }[/math]

Радикс

Каждый разряд обрабатывается устойчивой counting-сортировкой; индукция по разрядам (LSD) гарантирует правильный порядок после старшего разряда.

Сравнение с альтернативами

Критерий выбора	Что брать
Нужна устойчивость	Сортировка слиянием, Timsort, вставками, подсчётом
Нужна память [math]\displaystyle{ O(1) }[/math]	Пирамидальная сортировка, вставками, Быстрая сортировка
Нужна максимальная средняя скорость	Быстрая сортировка / introsort
Нужна адаптивность	Timsort
Нужна гарантия [math]\displaystyle{ O(n\log n) }[/math]	Сортировка слиянием, Пирамидальная сортировка, introsort
Целые ключи, малый диапазон	counting sort, radix
Равномерные ключи	bucket sort

Рис. 5. Полная таблица: время, память, устойчивость, применения.

Независимые свойства. Устойчивость, in-place, адаптивность и гарантия не связаны: нельзя получить всё сразу. Например, mergesort устойчив и гарантирован, но платит [math]\displaystyle{ O(n) }[/math] памяти; heapsort экономит память, но неустойчив.

Рис. 6. Четыре независимых свойства и их комбинации.

Где применяется

Стандартные библиотеки. std::sort (introsort — скорость и гарантия), std::stable_sort (слияние/Timsort), Python sorted/list.sort (Timsort), Java Arrays.sort (introsort для примитивов, Timsort для объектов). Почему: разные требования к устойчивости и памяти [1][5].

Системы реального времени и embedded. heapsort ([math]\displaystyle{ O(1) }[/math] памяти, гарантия) или сортировка вставками на малых данных. Почему: нельзя допустить худшего [math]\displaystyle{ \Theta(n^2) }[/math] и лишних буферов [2].

Большие данные и внешняя сортировка. Слияние и многопутевое слияние: данные на диске, важен последовательный доступ. Почему: слияние линейно и последовательно [2][3].

Целые/короткие фиксированные ключи. Counting и radix в гистограммах, кодировании, биоинформатике (сортировка последовательностей по суффиксам/префиксам). Почему: [math]\displaystyle{ O(n+k) }[/math] быстрее сравнений [1][5].

СУБД и аналитика. Sort-merge join, агрегации, оконные функции опираются на устойчивую сортировку и внешнее слияние. Почему: устойчивость и предсказуемость [3].

Рис. 7. Выбор диктуют устойчивость, память, гарантия и структура ключей.

Историческая справка

Сортировки — старейшая область алгоритмов. Пузырьковая и вставочная известны с первых лет вычислений; Shellsort предложил Дональд Шелл в 1959 году (обобщение вставок с шагами). Быструю сортировку изобрёл Тони Хоар (1961–1962) [6]; пирамидальную — Дж. Уильямс (1964) с линейным build-heap Р. Флойда (1964) [7]; слияние восходит к Джону фон Нейману (1945). Не-сравнительные сортировки уходят корнями в перфокарточные машины Холлерита (radix-сортировка, конец XIX века) и counting sort [5].

Нижняя граница [math]\displaystyle{ \Omega(n\log n) }[/math] через деревья решений — классический результат информационной теории; подробное изложение — Кнут, т. 3 [5], и CLRS, гл. 8 (сортировка за линейное время и нижняя граница) [1].

Типичные ошибки и подводные камни

Ожидание линейного времени от сравнительных сортировок. Невозможно (нижняя граница); [math]\displaystyle{ O(n) }[/math] достижим только вне модели сравнений.
Применение counting/radix к произвольным ключам. Нужны целые/ограниченный диапазон; иначе [math]\displaystyle{ k }[/math] велик, и сортировка медленна.
Неустойчивость там, где нужна устойчивость. Сортировка по составным ключам требует устойчивого алгоритма (mergesort/Timsort), а не quicksort/heapsort.
Игнорирование памяти. mergesort/Timsort требуют [math]\displaystyle{ O(n) }[/math]; в embedded берут heapsort.
Худший случай quicksort. На «анти-входах» — [math]\displaystyle{ \Theta(n^2) }[/math]; лечится рандомизацией/introsort.
Переполнение ключей в counting. Диапазон [math]\displaystyle{ k }[/math] и счётчики должны помещаться в тип.
Путаница [math]\displaystyle{ O(n) }[/math] и [math]\displaystyle{ O(n+k) }[/math]. Если [math]\displaystyle{ k \gg n }[/math], counting/radix проигрывают сравнениям.
Смешение 0- и 1-базной индексации в counting (позиции cnt[a[i]] - 1).
Сортировка маленьких массивов «тяжёлым» алгоритмом. На [math]\displaystyle{ n \lt 16 }[/math] вставки быстрее; гибриды так и делают.
Stable vs in-place trade-off. Нельзя одновременно иметь обе дешёвые; помните о компромиссе.

Задачи для практики

Нижняя граница. Докажите, что любая сравнительная сортировка делает [math]\displaystyle{ \Omega(n\log n) }[/math] сравнений. Подсказка: дерево решений и [math]\displaystyle{ n! }[/math].

Counting sort. Реализуйте устойчивую сортировку подсчётом и проверьте на дубликатах. Подсказка: проход справа налево.

Radix. Отсортируйте 32-битные числа поразрядно и сравните время с std::sort. Подсказка: 4 прохода по байтам.

Устойчивость. Определите, какие из quicksort/heapsort/mergesort/Timsort устойчивы, и приведите контрпример для неустойчивого.

Худший вход. Постройте вход, дающий quicksort [math]\displaystyle{ \Theta(n^2) }[/math], и проверьте подсчётом.

Гибрид. Скомбинируйте quicksort и сортировку вставками при [math]\displaystyle{ n \lt 16 }[/math]; сравните число сравнений.

Выбор. Для задачи «устойчиво отсортировать по двум ключам» выберите алгоритм и объясните. Подсказка: сначала по второстепенному, затем устойчиво по главному.

Оценка ключей. Когда counting sort быстрее mergesort? Выведите условие через [math]\displaystyle{ k }[/math] и [math]\displaystyle{ n }[/math]. Подсказка: [math]\displaystyle{ n + k }[/math] против [math]\displaystyle{ n\log n }[/math].

Связанные темы

Быстрая сортировка — средняя скорость, introsort.
Сортировка слиянием — устойчивость и гарантия.
Пирамидальная сортировка — гарантия при [math]\displaystyle{ O(1) }[/math] памяти.
Сортировка вставками — база гибридов; адаптивность и малые массивы.
Сортировка Шелла, Сортировка выбором, Сортировка пузырьком — элементарные сортировки-родственники.
Timsort — адаптивность и устойчивость.
Асимптотическая сложность — нижние границы и рекуррентности.
Графы — многие графовые задачи начинаются с сортировки рёбер/вершин.

Источники

Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms (CLRS). 3rd ed. — MIT Press, 2009. — Гл. 2, 6, 7, 8 (mergesort, heapsort, quicksort, сортировка за линейное время и нижняя граница).
Sedgewick R., Wayne K. Algorithms. 4th ed. — Addison-Wesley, 2011. — Гл. 2 (сортировки), приложения к внешней сортировке.
Silberschatz A., Korth H. F., Sudarshan S. Database System Concepts. — McGraw-Hill, 7th ed., 2019 (внешняя сортировка, sort-merge join).
Peters T. listsort.txt (Timsort). URL: https://github.com/python/cpython/blob/main/Objects/listsort.txt.
Knuth D. E. The Art of Computer Programming. Vol. 3: Sorting and Searching. — Addison-Wesley, 2nd ed., 1998 (алгоритмы, нижние границы, radix, внешняя сортировка).
Hoare C. A. R. Quicksort // The Computer Journal. — 1962. — Vol. 5, № 1.
Williams J. W. J. Algorithm 232: Heapsort // CACM. — 1964; Floyd R. W. Algorithm 245: Treesort // CACM. — 1964.
Wikipedia: Sorting algorithm. URL: https://en.wikipedia.org/wiki/Sorting_algorithm .

Поиск

Навигация