Алгоритмы сортировки

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

Сравнение

Алгоритм	Лучший	Средний	Худший	Память	Устойчивая	На месте
Пузырьком	n	n²	n²	1	да	да
Выбором	n²	n²	n²	1	нет	да
Вставками	n	n²	n²	1	да	да
Шелла	n log n	≈ n^1.25	n^1.5	1	нет	да
Слиянием	n	n log n	n log n	n	да	нет
Быстрая	n log n	n log n	n²	log n	нет	да
Пирамидальная	n log n	n log n	n log n	1	нет	да
Подсчётом	n + k	n + k	n + k	n + k	да	нет
Поразрядная	d(n + b)	d(n + b)	d(n + b)	n + b	да	нет

Везде имеется в виду O(…). k — диапазон значений, d — число цифр, b — основание (10).

Главные понятия

Сортировки сравнением (от пузырька до пирамидальной) задают только вопрос «a меньше b?». Любому такому алгоритму в худшем случае нужно не меньше ${\log }_{2}n!\approx n{\log }_{2}n$ сравнений: всего есть $n!$ возможных порядков, а каждое сравнение в лучшем случае делит их пополам. Поэтому O(n log n) — лучшее возможное: слияние и пирамидальная достигают его всегда, быстрая — в среднем.

Сортировки подсчётом и поразрядная не сравнивают элементы: они используют сами значения как индексы массива. Так они обходят n log n — но работают только с целыми числами (или ключами, которые можно превратить в целые).

Устойчивость — равные элементы сохраняют исходный порядок. Это важно, когда записи сортируют по нескольким ключам по очереди: отсортируйте людей по имени, потом устойчиво по возрасту — и люди одного возраста останутся в алфавитном порядке.

На месте — алгоритму нужно лишь O(1) (или O(log n)) дополнительной памяти, кроме самого массива.

Что выбрать

Ситуация	Выбор
Общий случай, быстрее всех в среднем	Быстрая
Нужна устойчивость или гарантированный n log n	Слиянием
Гарантированный n log n и O(1) памяти	Пирамидальная
Маленькие или почти отсортированные массивы	Вставками
Целые числа в небольшом диапазоне	Подсчётом
Много целых чисел с небольшим числом цифр	Поразрядная
Изучение основ	Пузырьком, выбором

В рабочем коде на JavaScript обычно правильный выбор — Array.prototype.sort (TimSort, гибрид слияния и вставок). Эта библиотека показывает, как устроены классические алгоритмы, и даёт надёжные реализации для учёбы, экспериментов и особых случаев.

Литература

• Кормен — Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. Алгоритмы: построение и анализ, 3-е изд., 2013 (Introduction to Algorithms, 4th ed., 2022). Главы 2, 6, 7, 8.
• Седжвик — Р. Седжвик, К. Уэйн. Алгоритмы на Java, 4-е изд., 2013. Глава 2.
• Кнут — Д. Кнут. Искусство программирования, т. 3: Сортировка и поиск, 2-е изд., 2000.