Сортировка упорядочивает элементы по выбранному признаку: числа — по величине, товары — по цене, записи — по дате. Элементы сохраняются, меняется только их порядок.
Начнём с трёх цен и простых способов расставить их по порядку. Затем перейдём к алгоритмам, которые работают с целыми группами предметов, сравним их поведение и разберёмся, как выбрать подходящий способ.
Пусть три предмета стоят 30, 10 и 20. Хотим расположить их от самого дешёвого к самому дорогому.
Массив — это последовательность элементов. Ключ сортировки — значение, по которому мы их упорядочиваем: здесь это цена. Переставляем предмет целиком, вместе с его ценой. Буквой N обозначаем число элементов массива; в этом примере N = 3.
Сравнение отвечает на вопрос, какая из двух цен меньше. При перемещении записываем предмет на новое место; при обмене двух предметов записываются две ячейки массива. В примерах ниже сравнения и записи считаются отдельно.
Сначала следите за схемой и пояснением текущего шага: какие предметы сравниваются, какие уже заняли окончательные места. Код описывает те же действия. К нему и к оценкам сложности можно вернуться, когда станет понятна сама идея.
Задайте один массив для всех восьми сортировок. Так можно сравнить, сколько работы каждой нужно для одного и того же результата.
Этот массив общий для всех восьми сортировок. Изменение данных возвращает все примеры к первому шагу.
Порядок влияет на число действий: на уже упорядоченном массиве пузырьковая сортировка завершится за один проход, на обратном — потребуется больше проходов.
Первые три способа наводят порядок постепенно, по одному предмету. Начнём с самого простого действия: сравним двух соседей.
Сравниваем соседей и меняем их местами, если левый больше. После каждого прохода самое большое из оставшихся значений оказывается справа.
Если за проход не было ни одного обмена, массив уже упорядочен. Заканчиваем сразу.
Переставляем предметы в исходном массиве. Дополнительно нужны только несколько индексов и временное значение для обмена. Их количество не растёт вместе с массивом — O(1).
Если предмет А стоил 20 и стоял раньше предмета Б с той же ценой, после сортировки А останется раньше Б. Такое сохранение порядка называют устойчивостью. Оно полезно, когда у предметов есть и другие свойства, кроме цены.
Этот массив общий для всех восьми сортировок. Изменение данных возвращает все примеры к первому шагу.
Метки A, B… отличают предметы с равной стоимостью. Сравниваем только число; следите, сохранится ли порядок меток.
Оценка сложности описывает, как растёт объём работы алгоритма при увеличении количества данных. Здесь N — число элементов массива. Лучший и худший случаи показывают, как исходные данные могут облегчить или усложнить работу.
Если массив уже упорядочен, достаточно одного прохода, чтобы это проверить. Иначе проходов может понадобиться много: снова и снова сравниваем соседей. С ростом массива увеличивается и длина прохода, и возможное число проходов.
В полном наборе проходов может быть (N − 1) + (N − 2) + … + 1 = N(N − 1) / 2 сравнений. Если массив уже упорядочен, достаточно первого прохода: N − 1 сравнений и ни одного обмена. Но ранний выход помогает не всегда. Маленький элемент в самом конце массива за один проход сдвигается влево лишь на одну позицию, даже если остальные элементы уже стоят по порядку.
В пузырьковой сортировке большое значение добирается до конца через обмены с соседями. Теперь поступим иначе: сначала найдём самый маленький из оставшихся предметов, а затем сразу поставим его на нужное место.
Находим минимум в оставшейся части массива и переносим его в начало этой части. Затем повторяем поиск для следующей позиции.
Обменов немного, но минимум каждый раз приходится искать заново. Даже уже упорядоченный массив требует всех сравнений.
Переставляем предметы в исходном массиве. Дополнительно нужны только несколько индексов и временное значение для обмена. Их количество не растёт вместе с массивом — O(1).
Два предмета с ценой 20 могут поменяться местами относительно друг друга. По цене результат всё равно правильный, но прежний порядок равных предметов не гарантирован. Такую сортировку называют неустойчивой.
Этот массив общий для всех восьми сортировок. Изменение данных возвращает все примеры к первому шагу.
Метки A, B… отличают предметы с равной стоимостью. Сравниваем только число; следите, сохранится ли порядок меток.
Оценка сложности описывает, как растёт объём работы алгоритма при увеличении количества данных. Здесь N — число элементов массива. Лучший и худший случаи показывают, как исходные данные могут облегчить или усложнить работу.
Для каждого минимума приходится просматривать все оставшиеся предметы, даже если они уже стоят по порядку. Необработанная часть постепенно сокращается, но для каждой новой позиции поиск начинается заново.
Чтобы найти первый минимум, нужно N − 1 сравнений, следующий — N − 2, и так далее. При любом исходном порядке сумма равна N(N − 1) / 2. Обменов при этом не больше N − 1. Поэтому небольшое число записей ещё не означает, что алгоритм выполняет мало работы.
Сортировка выбором ищет следующий минимум среди оставшихся предметов. Сортировка вставками берёт очередной предмет и находит ему место среди уже обработанных.
Слева поддерживаем упорядоченную часть. Берём следующий предмет и двигаем его влево, пока он не займёт подходящее место — как карту в руке.
Здесь вставка показана через обмены с соседями. Равные значения не меняем местами. Хорошо видно, почему почти упорядоченный массив требует мало работы.
Переставляем предметы в исходном массиве. Дополнительно нужны только несколько индексов и временное значение для обмена. Их количество не растёт вместе с массивом — O(1).
Если предмет А стоил 20 и стоял раньше предмета Б с той же ценой, после сортировки А останется раньше Б. Такое сохранение порядка называют устойчивостью. Оно полезно, когда у предметов есть и другие свойства, кроме цены.
Этот массив общий для всех восьми сортировок. Изменение данных возвращает все примеры к первому шагу.
Метки A, B… отличают предметы с равной стоимостью. Сравниваем только число; следите, сохранится ли порядок меток.
Оценка сложности описывает, как растёт объём работы алгоритма при увеличении количества данных. Здесь N — число элементов массива. Лучший и худший случаи показывают, как исходные данные могут облегчить или усложнить работу.
Если очередной предмет уже на подходящем месте, достаточно короткой проверки. При обратном порядке каждый новый предмет проходит через всю упорядоченную часть. Почти упорядоченные данные обычно требуют гораздо меньше перемещений.
Это можно описать точнее. Инверсия — пара, в которой больший элемент стоит раньше меньшего. Каждый обмен соседей устраняет одну такую пару. Если инверсий I, работа этого варианта оценивается как O(N + I). В упорядоченном массиве их нет, а при обратном порядке разных значений их N(N − 1) / 2 — отсюда квадратичный худший случай.
До этого мы пристраивали отдельные предметы. Теперь будем объединять целые упорядоченные участки. В каждом из них следующий наименьший предмет всегда находится в начале.
Например, из участков [10, 30] и [20, 40] получится [10, 20, 30, 40]. Сначала выбираем 10, затем 20, потом 30 и переносим оставшееся 40. Результат собираем в буфере — временном массиве.
Участок из одного элемента уже упорядочен. Сливаем соседние упорядоченные участки длиной 1, затем 2, 4 и так далее. Каждый раз берём меньший из следующих доступных ключей, а при равенстве выбираем предмет из левого участка.
Здесь слияние идёт снизу вверх — от коротких участков к длинным. Временный массив buffer виден под основным. rightStart — начало правого участка, pairEnd — последний индекс объединяемой пары. Когда один участок закончился, переносим остаток другого без сравнений ключей. Затем записываем буфер обратно.
При слиянии временно складываем предметы в отдельный буфер, затем переносим обратно. Буфер может вместить весь массив: вдвое больше предметов — вдвое больше места. Дополнительная память — O(N).
Если предмет А стоил 20 и стоял раньше предмета Б с той же ценой, после сортировки А останется раньше Б. Такое сохранение порядка называют устойчивостью. Оно полезно, когда у предметов есть и другие свойства, кроме цены.
Этот массив общий для всех восьми сортировок. Изменение данных возвращает все примеры к первому шагу.
Буфер заполняется по мере выполнения.
Метки A, B… отличают предметы с равной стоимостью. Сравниваем только число; следите, сохранится ли порядок меток.
Оценка сложности описывает, как растёт объём работы алгоритма при увеличении количества данных. Здесь N — число элементов массива. Лучший и худший случаи показывают, как исходные данные могут облегчить или усложнить работу.
За один проход обрабатываем массив, объединяя короткие упорядоченные участки в более длинные. Удвоение массива добавляет всего один проход слияния. В показанном варианте эти проходы выполняются и на уже упорядоченных данных.
Длины участков удваиваются: 1, 2, 4 и так далее. Число проходов растёт как log₂ N, на каждом выполняется O(N) работы. Вместе получаем O(N log N) для лучшего, среднего и худшего случаев. При равных ценах берём предмет из левого участка — так равные предметы сохраняют прежний порядок.
Слияние объединяет упорядоченные части. Быстрая сортировка сначала разделяет предметы на части: выбирает значение для сравнения — опорное — и отделяет меньшие значения от остальных.
После установки опорного обе части ещё нужно упорядочить. В каждой повторяем тот же приём, пока не останутся части из одного предмета или пустые. Когда функция решает уменьшенные версии своей же задачи, это называют рекурсией.
Выбираем последнее значение опорным. Собираем меньшие значения слева, ставим опорное на своё место и отдельно упорядочиваем две получившиеся части.
Внизу кода вызываем quickSort для всего массива. Каждый вложенный вызов получает свои firstIndex и lastIndex — границы части включительно. Это разбиение Ломуто: опорный всегда последний. В среднем при равновероятных перестановках различных значений — O(N log N); на упорядоченных данных возможен O(N²). Память указана для стека вызовов в худшем случае.
Новый массив не создаём, но для вложенных вызовов quickSort сохраняются границы частей. В худшем случае глубина вызовов растёт до N, поэтому стек требует O(N) дополнительного места.
Два предмета с ценой 20 могут поменяться местами относительно друг друга. По цене результат всё равно правильный, но прежний порядок равных предметов не гарантирован. Такую сортировку называют неустойчивой.
Этот массив общий для всех восьми сортировок. Изменение данных возвращает все примеры к первому шагу.
Метки A, B… отличают предметы с равной стоимостью. Сравниваем только число; следите, сохранится ли порядок меток.
Оценка сложности описывает, как растёт объём работы алгоритма при увеличении количества данных. Здесь N — число элементов массива. Лучший и худший случаи показывают, как исходные данные могут облегчить или усложнить работу.
От опорного зависит, насколько равномерно разделится работа. Примерно равные части быстро становятся маленькими. Если же одна часть каждый раз пуста, а в другой остаётся почти весь массив, приходится снова просматривать большой участок.
Разбиение одного участка требует линейного прохода. Если части примерно равны, получается около log₂ N уровней с O(N) работы на каждом. Если же раз за разом возникают части размером 0 и N − 1, число сравнений складывается в (N − 1) + … + 1 = O(N²). Именно так здесь ведут себя упорядоченный массив, обратный порядок и одинаковые ключи. При сбалансированных разбиениях стек занимает O(log N), а в худшем случае — O(N).
Сортировка выбором каждый раз заново ищет крайнее значение. Пирамидальная сортировка заранее организует оставшиеся предметы так, чтобы наибольший было легко найти.
На схеме массив дополнительно изображён деревом. Самый верхний элемент — корень. Элемент, от которого вниз идут ветви, называют родителем, а связанные с ним элементы ниже — детьми. Это связи между позициями в массиве: сами предметы по-прежнему хранятся в нём в одном экземпляре.
В куче, которую строим здесь, каждый родитель не меньше своих детей. Поэтому максимум оказывается в корне, хотя весь массив ещё не отсортирован. Переносим максимум в конец и восстанавливаем это правило, чтобы найти следующий.
Сначала строим кучу в исходном массиве. Затем переносим максимум из корня в конец, уменьшаем кучу и восстанавливаем её порядок перед следующим извлечением.
Дерево и столбцы показывают одни и те же элементы, а не две копии в памяти. siftDown раскрыт в коде: выбираем ребёнка с большим ключом и опускаем родителя, пока порядок в куче не восстановится. Построение кучи — O(N), все извлечения вместе — O(N log N) в худшем случае. Если все ключи равны, каждый спуск заканчивается сразу: лучший случай этой реализации — O(N).
Переставляем предметы в исходном массиве. Дополнительно нужны только несколько индексов и временное значение для обмена. Их количество не растёт вместе с массивом — O(1).
Два предмета с ценой 20 могут поменяться местами относительно друг друга. По цене результат всё равно правильный, но прежний порядок равных предметов не гарантирован. Такую сортировку называют неустойчивой.
Этот массив общий для всех восьми сортировок. Изменение данных возвращает все примеры к первому шагу.
Метки A, B… отличают предметы с равной стоимостью. Сравниваем только число; следите, сохранится ли порядок меток.
Оценка сложности описывает, как растёт объём работы алгоритма при увеличении количества данных. Здесь N — число элементов массива. Лучший и худший случаи показывают, как исходные данные могут облегчить или усложнить работу.
Куча позволяет не искать каждый максимум по всему оставшемуся массиву. После извлечения восстанавливаем порядок вдоль одного пути вниз по дереву. С ростом кучи этот путь удлиняется, но гораздо медленнее, чем растёт число предметов.
Построение кучи снизу вверх занимает O(N): большинство узлов находится близко к листьям, и опускать их далеко не приходится. После этого каждое из N − 1 извлечений может потребовать O(log N) работы для восстановления порядка. Если все ключи равны, каждый спуск сразу заканчивается. Поэтому лучший случай этой реализации — O(N).
Предыдущие шесть способов определяли порядок, сравнивая цены между собой. Если цены — целые неотрицательные числа в небольшом диапазоне, можно посчитать, сколько раз встречается каждая.
В массиве [2, 1, 2] цена 1 встречается один раз, а цена 2 — дважды. Значит, в результате нужно одно место для цены 1, а следом — два места для цены 2.
Складываем количества по порядку и получаем 1, затем 3. Это накопленные суммы: один предмет стоит не дороже 1, а все три — не дороже 2. Они показывают, где заканчивается каждая группа цен. По этим границам размещаем исходные предметы во временном массиве, сохраняя порядок предметов с равными ценами.
Считаем, сколько раз встретилась каждая стоимость. По накопленным суммам находим места для предметов в буфере, затем переносим их обратно. Порядок получаем из самих цен и количества предметов с каждой ценой.
Сначала проходим массив, чтобы найти максимум. Таблица сначала хранит частоты, затем границы групп. Размещаем предметы справа налево и уменьшаем границу: так равные предметы сохраняют исходный порядок. Большой диапазон стоимостей требует много пустых ячеек, даже если сам массив короткий.
Нужны таблица из K счётчиков и буфер из N предметов: O(N + K). Ячейки таблицы видны на схеме, включая нулевые частоты. Это место сверх исходного массива.
Если предмет А стоил 20 и стоял раньше предмета Б с той же ценой, после сортировки А останется раньше Б. Такое сохранение порядка называют устойчивостью. Оно полезно, когда у предметов есть и другие свойства, кроме цены.
Этот массив общий для всех восьми сортировок. Изменение данных возвращает все примеры к первому шагу.
Буфер заполняется по мере выполнения.
Метки A, B… отличают предметы с равной стоимостью. Сравниваем только число; следите, сохранится ли порядок меток.
Оценка сложности описывает, как растёт объём работы алгоритма при увеличении количества данных. Здесь N — число элементов массива. Лучший и худший случаи показывают, как исходные данные могут облегчить или усложнить работу.
Объём работы зависит от двух размеров: числа предметов и размера таблицы цен. Даже короткий массив может потребовать много работы, если самая большая цена заставляет завести огромную таблицу.
K — число ячеек таблицы: от 0 до максимальной стоимости включительно. Здесь ключи — целые неотрицательные числа.
Поиск максимума, подсчёт частот, размещение предметов и перенос результата обратно требуют по O(N) работы. Заполнение таблицы нулями и вычисление накопленных сумм — O(K). Вместе получаем O(N + K) времени и дополнительной памяти. Размещение справа налево сохраняет порядок предметов с равными ключами. В этой реализации K включает и те значения от нуля до максимума, которых нет в массиве.
Для подсчёта нужна таблица на весь диапазон цен. Поразрядная сортировка рассматривает по одной цифре за раз, поэтому на каждом проходе ей достаточно десяти корзин — от 0 до 9.
Возьмём 23, 12, 21 и 13. Сначала соберём числа по цифре единиц, как показано ниже. Затем — по десяткам, сохраняя уже сложившийся порядок внутри каждой корзины.
В корзине с десятком 1 число 12 уже стоит перед 13, а в корзине с десятком 2 число 21 стоит перед 23. Это результат предыдущего прохода. Сохранив этот порядок, мы используем уже проделанную работу; произвольная перестановка внутри корзины могла бы её разрушить.
Сначала раскладываем предметы по цифре единиц, затем по цифре десятков. На каждом проходе собираем корзины от 0 до 9, сохраняя порядок предметов внутри каждой.
Это LSD-вариант: от младшего разряда к старшему. Подсвечена цифра, которую читаем сейчас; у однозначных чисел цифра десятков равна нулю. Сохранение порядка внутри корзин позволяет следующему проходу учитывать результат предыдущего. append добавляет предмет в конец корзины.
Десять корзин вместе хранят N предметов: O(N + B), где B = 10. После сбора корзины переиспользуются на следующем разряде.
Если предмет А стоил 20 и стоял раньше предмета Б с той же ценой, после сортировки А останется раньше Б. Такое сохранение порядка называют устойчивостью. Оно полезно, когда у предметов есть и другие свойства, кроме цены.
Этот массив общий для всех восьми сортировок. Изменение данных возвращает все примеры к первому шагу.
Буфер заполняется по мере выполнения.
Метки A, B… отличают предметы с равной стоимостью. Сравниваем только число; следите, сохранится ли порядок меток.
Оценка сложности описывает, как растёт объём работы алгоритма при увеличении количества данных. Здесь N — число элементов массива. Лучший и худший случаи показывают, как исходные данные могут облегчить или усложнить работу.
Каждый разряд требует ещё одного прохода по всем предметам. Больше предметов — длиннее каждый проход; больше цифр в ценах — больше проходов. Число корзин для десятичных цифр остаётся равным десяти.
D — число разрядов максимального значения, B = 10 — число корзин. В примерах целые положительные значения до 99, поэтому нужен один или два прохода.
За один проход распределяем N предметов по корзинам, затем собираем их, обходя B корзин. Это O(N + B) работы на разряд. Всего разрядов D, поэтому оценка равна O(D · (N + B)). Порядок добавления внутри корзин сохраняется, и следующий проход не теряет результат предыдущего. Во всех корзинах вместе лежит N предметов, поэтому дополнительная память — O(N + B).
«Сравнения» — проверки двух значений, включая поиск максимума. «Записи» — перенос предмета в массив, буфер или корзину; обмен — две записи. Обращения к counts считаем отдельно: чтение и запись — по одному, включая заполнение нулями. Выделение цифры нужного разряда — ещё один отдельный счётчик. Изменение индексов, проверки условий циклов и выделение памяти сюда не входят. Это не полное число инструкций и не замер времени. Прочерк означает, что алгоритм не использует такую операцию.
Результаты полного выполнения на выбранных выше данных. Количество шагов анимации и скорость воспроизведения не используются для сравнения.
| Алгоритм | Сравнения | Записи | Обращения к таблице | Выделения цифр |
|---|---|---|---|---|
| Пузырьковая сортировка | — | — | — | — |
| Сортировка выбором | — | — | — | — |
| Сортировка вставками | — | — | — | — |
| Сортировка слиянием | — | — | — | — |
| Быстрая сортировка | — | — | — | — |
| Пирамидальная сортировка | — | — | — | — |
| Сортировка подсчётом | — | — | — | — |
| Поразрядная сортировка | — | — | — | — |
«Сравнения» — проверки двух значений, включая поиск максимума. «Записи» — перенос предмета в массив, буфер или корзину; обмен — две записи. Обращения к counts считаем отдельно: чтение и запись — по одному, включая заполнение нулями. Выделение цифры нужного разряда — ещё один отдельный счётчик. Изменение индексов, проверки условий циклов и выделение памяти сюда не входят. Это не полное число инструкций и не замер времени. Прочерк означает, что алгоритм не использует такую операцию.
Попробуйте уже упорядоченный массив, затем обратный. Пузырьковая сортировка завершится раньше на первом, а выбором всё равно проверит все оставшиеся значения. Быстрая сортировка здесь выбирает последний элемент опорным — порядок данных для неё особенно важен.
Счётчики помогают сравнить работу на выбранном массиве. Но для выбора алгоритма важны и другие вопросы: что произойдёт с равными предметами, понадобится ли дополнительное место и как вырастет работа на большем массиве.
Пусть предметы поступили в таком порядке: зелье A (20), меч (10), зелье B (20). После устойчивой сортировки по цене получится: меч (10), зелье A (20), зелье B (20). Два зелья сохранят порядок поступления. Неустойчивая сортировка может поставить зелье B раньше зелья A.
Ключ сортировки здесь только один — цена. Метки A и B помогают различать предметы, но не участвуют в сравнении. Выберите «С повторами» или «Все значения равны» и проследите за метками. Если порядок сохранился в одном запуске, это ещё не доказывает устойчивость алгоритма.
Пузырьковая сортировка переставляет предметы в исходном массиве. Для обмена достаточно временно запомнить один предмет; длиннее массив — больше такого места не нужно. Это O(1) дополнительной памяти. Слияние собирает результат во временном массиве: для вдвое большего числа предметов понадобится вдвое больше места — O(N).
Дополнительное место бывает нужно и без второго массива. Быстрая сортировка запоминает незавершённые вызовы функции, пока обрабатывает вложенные части. Эти записи хранятся в стеке вызовов и тоже учитываются в расходе памяти.
Оценки относятся к показанным реализациям. Считаем, что сравнение двух ключей и перемещение предмета фиксированного размера занимают постоянное время. В дополнительную память входят временные буферы и стек вызовов, но не исходный массив и не данные для анимации.
| Алгоритм | Лучший | Средний* | Худший | Доп. память† | Устойчивая |
|---|---|---|---|---|---|
| Пузырьковая сортировка | O(N) | O(N²) | O(N²) | O(1) | Да |
| Сортировка выбором | O(N²) | O(N²) | O(N²) | O(1) | Нет |
| Сортировка вставками | O(N) | O(N²) | O(N²) | O(1) | Да |
| Сортировка слиянием | O(N log N) | O(N log N) | O(N log N) | O(N) | Да |
| Быстрая сортировка | O(N log N) | O(N log N) | O(N²) | O(N) | Нет |
| Пирамидальная сортировка | O(N) | O(N log N) | O(N log N) | O(1) | Нет |
| Сортировка подсчётом | O(N + K) | O(N + K) | O(N + K) | O(N + K) | Да |
| Поразрядная сортировка | O(D · (N + B)) | O(D · (N + B)) | O(D · (N + B)) | O(N + B) | Да |
* Для шести сортировок на сравнениях предполагаем, что все перестановки различных ключей равновероятны. У сортировок подсчётом и поразрядной оценки выражены через N, K, D и B и не зависят от исходного порядка. Лучший случай O(N) у пирамидальной сортировки достигается при равных ключах; если все ключи различны, её лучший случай — O(N log N).
† Здесь указана память в худшем случае. В частности, быстрая сортировка в этом варианте может занять O(N) места в стеке, хотя при сбалансированных разбиениях ей достаточно O(log N).
Выбор зависит от данных и требований. Счётчики выше показывают один конкретный запуск; оценка сложности описывает рост работы.
Сортировка вставками
Сравните наборы «Почти по порядку» и «Минимум в конце». Сортировка вставками быстро справится с обоими. А пузырьковая будет передвигать минимум из конца влево лишь на одну позицию за проход — ранний выход здесь не поможет.
Устойчивая сортировка, если важен порядок равных ключей
Попробуйте слияние, а для подходящих ключей — подсчёт или поразрядную сортировку. Выберите «С повторами» или «Все значения равны» и проследите за метками. В быстрой сортировке с последним опорным равные ключи приводят к неравномерным разбиениям.
Подсчётом
Выберите «Узкий диапазон». При том же N таблица меньше. Для редких огромных ключей её размер может перечеркнуть преимущество.
Поразрядная
Сравните проход по единицам и по десяткам. Стоимость зависит и от N, и от числа разрядов.
Слиянием или пирамидальная
Слияние сохраняет порядок равных, но требует буфера. Куча работает внутри массива и этот порядок не гарантирует.
В прикладном коде обычно начинают с библиотечной сортировки и проверяют её гарантии. Эти примеры помогают понять требования и поведение алгоритма, а не выбрать победителя по скорости анимации.
Основные идеи уже разобраны. Здесь — условия оценок, объяснение границы для сортировок на сравнениях и приёмы, которые используют в практических реализациях.
Детали реализации имеют значение: здесь показаны слияние снизу вверх и разбиение Ломуто с последним элементом в качестве опорного.
Сортировка на сравнениях узнаёт порядок, сравнивая ключи между собой. Для N различных ключей возможны N! исходных порядков. Чтобы различить их все, двоичное дерево решений должно иметь путь длиной не меньше log₂(N!) = Θ(N log N). В худшем случае потребуется не меньше этого числа сравнений.
Сортировки подсчётом и поразрядная используют ещё и устройство самих ключей: их значения служат индексами таблицы или разбираются по цифрам. Поэтому нижняя граница для одних только сравнений к ним не относится. Но преимущество зависит от данных: широкий диапазон увеличивает K, а длинные ключи — D. Универсальной заменой сортировкам на сравнениях эти методы не становятся.
Случайный выбор опорного делает быструю сортировку менее зависимой от исходного порядка, но не устраняет квадратичный худший случай. Разбиение на три части отдельно собирает ключи меньше опорного, равные ему и больше него. Так не приходится снова обрабатывать большую группу одинаковых ключей.
Гибридные алгоритмы объединяют полезные свойства разных сортировок. Introsort при слишком глубокой рекурсии переходит от быстрой сортировки к пирамидальной и тем самым сохраняет оценку O(N log N) в худшем случае. TimSort находит упорядоченные участки, дополняет короткие участки сортировкой вставками и объединяет их устойчивым слиянием. У библиотечной сортировки стоит проверить именно её гарантии: сложность, устойчивость и требования к функции сравнения.