Введение

Алгоритм, упорядочивающий списки

В информатике алгоритм сортировки — это алгоритм, который располагает элементы списка в определенном порядке. Наиболее часто используемыми порядками являются числовой и лексикографический, а также порядок по возрастанию или убыванию. Эффективная сортировка важна для оптимизации работы других алгоритмов (например, поиска и слияния), которым требуются отсортированные входные данные. Сортировка также часто полезна для приведения данных к каноническому виду и для получения удобочитаемого вывода. Формально, результат работы любого алгоритма сортировки должен соответствовать двум условиям:
Результат должен быть в монотонном порядке (каждый элемент не меньше/не больше предыдущего, в соответствии с заданным порядком). Результат должен являться перестановкой (изменением порядка, но сохранением всех исходных элементов) входных данных. Для достижения оптимальной производительности входные данные следует хранить в структуре данных, обеспечивающей произвольный доступ, а не только последовательный.

История и понятия

С самого начала развития вычислительной техники проблема сортировки привлекала значительное внимание исследователей, возможно, из-за сложности её эффективного решения, несмотря на простоту и понятность постановки задачи. Среди авторов ранних алгоритмов сортировки, появившихся примерно в 1951 году, была Бетти Холбертон, работавшая над ENIAC и UNIVAC. Алгоритм сортировки пузырьком был проанализирован уже в 1956 году. Асимптотически оптимальные алгоритмы известны с середины XX века, и новые алгоритмы продолжают разрабатываться: широко используемый Timsort был создан в 2002 году, а библиотечная сортировка впервые опубликована в 2006 году. Алгоритмы сортировки, основанные на сравнениях, имеют фундаментальное ограничение в Ω(n log n) сравнений (для некоторых входных последовательностей потребуется кратное n log n сравнений, где n – количество элементов в сортируемом массиве). Алгоритмы, не использующие сравнения, такие как сортировка подсчётом, могут демонстрировать более высокую производительность. Алгоритмы сортировки широко представлены в вводных курсах компьютерных наук, где их разнообразие позволяет мягко ознакомиться с ключевыми алгоритмическими концепциями, такими как нотация «большое O», алгоритмы «разделяй и властвуй», структуры данных, такие как кучи и двоичные деревья, рандомизированные алгоритмы, анализ наилучшего, наихудшего и среднего случаев, компромиссы между временем и памятью, а также верхние и нижние оценки. Оптимальная сортировка небольших массивов (с минимальным количеством сравнений и обменов) или быстрая сортировка (с учётом особенностей конкретной аппаратной платформы) остаётся открытой исследовательской проблемой, решения для которой известны лишь для очень маленьких массивов (менее 20 элементов). Аналогично, оптимальная (в различных определениях) сортировка на параллельных вычислительных системах также является актуальной областью исследований.

Стабильность

Стабильные алгоритмы сортировки сортируют равные элементы в том же порядке, в котором они встречаются во входных данных. Например, в примере сортировки карт справа, карты сортируются по достоинству, а масть игнорируется. Это позволяет получить несколько правильно отсортированных версий исходного списка. Стабильные алгоритмы сортировки выбирают одну из них в соответствии со следующим правилом: если два элемента сравниваются как равные (например, две карты с достоинством 5), то их относительный порядок будет сохранен, то есть если один элемент предшествует другому во входных данных, он будет предшествовать ему и в выходных данных. Стабильность важна для сохранения порядка при многократной сортировке одного и того же набора данных. Например, предположим, что записи о студентах, состоящие из имени и номера группы, сортируются динамически, сначала по имени, затем по номеру группы. Если в обоих случаях используется стабильный алгоритм сортировки, то сортировка по номеру группы не изменит порядок имен; при использовании нестабильного алгоритма сортировка по группам может изменить порядок имен, в результате чего список студентов не будет отсортирован по алфавиту. Более формально, данные, подлежащие сортировке, могут быть представлены в виде записи или кортежа значений, а часть данных, используемая для сортировки, называется ключом. В примере с картами карты представлены как запись (достоинство, масть), а ключом является достоинство. Алгоритм сортировки считается стабильным, если для любых двух записей R и S с одинаковым ключом, при условии, что R предшествует S в исходном списке, R всегда будет предшествовать S в отсортированном списке. Когда равные элементы неразличимы, например, целые числа, или, в более общем случае, когда весь элемент является ключом, стабильность не имеет значения. Стабильность также не имеет значения, если все ключи различны. Нестабильные алгоритмы сортировки могут быть специально реализованы как стабильные. Один из способов сделать это — искусственно расширить сравнение ключей, чтобы сравнения между двумя объектами с одинаковыми ключами определялись порядком элементов во входном списке в качестве решающего фактора. Однако запоминание этого порядка может потребовать дополнительных затрат времени и памяти. Одно из применений стабильных алгоритмов сортировки — сортировка списка с использованием первичного и вторичного ключей. Например, предположим, что мы хотим отсортировать колоду карт так, чтобы масти шли в порядке треф (♣), бубен (♦), червей (♥), пик (♠), а внутри каждой масти карты сортировались по достоинству. Это можно сделать, сначала отсортировав карты по достоинству (используя любой алгоритм сортировки), а затем выполнив стабильную сортировку по масти:

Внутри каждой масти стабильная сортировка сохраняет порядок по достоинству, который уже был установлен. Эта идея может быть расширена на любое количество ключей и используется в поразрядной сортировке. Того же эффекта можно достичь с помощью нестабильной сортировки, используя лексикографическое сравнение ключей, которое, например, сначала сравнивает по масти, а затем по достоинству, если масти одинаковы.

Сравнение алгоритмов

В этих таблицах n — количество записей для сортировки. Столбцы "Лучший", "Средний" и "Худший" указывают временную сложность в каждом случае, при условии, что длина каждого ключа постоянна, и, следовательно, все сравнения, перестановки и другие операции могут выполняться за постоянное время. "Память" обозначает объем дополнительной памяти, необходимый помимо памяти, используемой самим списком, при том же условии. Указанные времена выполнения и требования к памяти представлены в нотации "большое O", поэтому основание логарифмов не имеет значения. Обозначение log^(2) n означает (log n)^(2).

Сравнительные сорта

Ниже приведена таблица алгоритмов сортировки. Сортировка сравнением не может работать лучше, чем O(n log n) в среднем. + Сравнение сортировок Наименование Лучшее Среднее Худшее Память Стабильность Метод Дополнительные примечания Сортировка слиянием на месте — — Да Слияние Может быть реализована как стабильная сортировка на основе стабильного слияния на месте. Сортировка кучей Нет Выбор Introsort Нет Разбиение и выбор Используется в нескольких реализациях STL. Сортировка слиянием Да Слияние Высоко параллелизуема (до O(log n) с использованием алгоритма "Трёх венгров"). Турнирная сортировка Нет Выбор Вариация сортировки кучей. Сортировка деревом Да Вставка При использовании самобалансирующегося двоичного дерева поиска. Блочная сортировка Да Вставка и слияние Комбинирует блочную сортировку слиянием на месте со сложностью O(n) с сортировкой слиянием снизу вверх. Smoothsort Нет Выбор Адаптивная вариация сортировки кучей, основанная на последовательности Леонардо, а не на традиционной бинарной куче. Timsort Да Вставка и слияние Выполняет n-1 сравнений, когда данные уже отсортированы или отсортированы в обратном порядке. Сортировка терпением Нет Вставка и выбор Находит все самые длинные возрастающие подпоследовательности за O(n log n). Cubesort Да Вставка Выполняет n-1 сравнений, когда данные уже отсортированы или отсортированы в обратном порядке. Быстрая сортировка Нет Разбиение Быстрая сортировка обычно выполняется на месте с использованием стека размером O(log n). Библиотечная сортировка Нет Вставка Похожа на сортировку вставками с пропуском. Требует случайной перестановки входных данных для гарантирования временных ограничений с высокой вероятностью, что делает её нестабильной. Shellsort Нет Вставка Малый размер кода. Comb sort Нет Перестановка В среднем быстрее, чем сортировка пузырьком. Сортировка вставками Да Вставка O(n + d) в худшем случае для последовательностей с d инверсиями. Сортировка пузырьком Да Перестановка Малый размер кода. Сортировка коктейлем Да Перестановка Вариация сортировки пузырьком, хорошо работающая с малыми значениями в конце списка. Gnome sort Да Перестановка Малый размер кода. Сортировка нечётными–чётными Да Перестановка Может быть легко запущена на параллельных процессорах. Простая сортировка блинами Нет Выбор Вариация сортировки выбором, использующая развороты вместо простой перестановки двух элементов после каждого сканирования выбора. Strand sort Да Выбор Сортировка выбором Нет Выбор Стабильна при использовании O(n) дополнительного пространства (связанные списки) или при реализации как вариация сортировки вставками вместо перестановки двух элементов. Сортировка обменом Нет Перестановка Малый размер кода. Циклическая сортировка Нет Выбор Сортировка на месте с теоретически оптимальным количеством записей.

Популярные алгоритмы сортировки

Хотя существует большое количество алгоритмов сортировки, в практических реализациях преобладают лишь несколько. Сортировка вставками широко используется для небольших наборов данных, а для больших наборов данных применяется асимптотически эффективная сортировка, в первую очередь сортировка кучей, сортировка слиянием или быстрая сортировка. Эффективные реализации обычно используют гибридный алгоритм, сочетающий асимптотически эффективный алгоритм для общей сортировки с сортировкой вставками для небольших списков на нижнем уровне рекурсии. Высокооптимизированные реализации используют более сложные варианты, такие как Timsort (сортировка слиянием, сортировка вставками и дополнительная логика), применяемый в Android, Java и Python, и introsort (быстрая сортировка и сортировка кучей), используемый (в различных вариантах) в некоторых реализациях сортировки C++ и .NET. Для более ограниченных данных, таких как числа в фиксированном интервале, широко используются распределяющие сортировки, такие как сортировка подсчётом или поразрядная сортировка. Сортировка пузырьком и её варианты редко используются на практике, но часто встречаются в обучении и теоретических обсуждениях. При физической сортировке объектов (например, алфавитной сортировке документов, тестов или книг) люди интуитивно обычно используют сортировку вставками для небольших наборов. Для больших наборов люди часто сначала разделяют объекты на группы, например, по первой букве, а многоуровневое разделение позволяет практически сортировать очень большие наборы. Часто пространство относительно недорого, например, можно разложить объекты на полу или на большой площади, но операции дороги, особенно перемещение объекта на большое расстояние – важна локальность данных. Сортировка слиянием также практична для физических объектов, особенно поскольку можно использовать две руки, по одной для каждого списка при слиянии, в то время как другие алгоритмы, такие как сортировка кучей или быстрая сортировка, плохо подходят для ручного использования. Другие алгоритмы, такие как библиотечная сортировка, вариант сортировки вставками, оставляющий промежутки, также практичны для физического использования.

Простые виды

Два из самых простых алгоритмов — сортировка вставками и сортировка выбором, оба из которых эффективны для небольших объемов данных благодаря низкой накладной стоимости, но неэффективны для больших объемов данных. Сортировка вставками, как правило, быстрее сортировки выбором на практике из-за меньшего числа сравнений и хорошей производительности на почти отсортированных данных, и поэтому предпочтительнее на практике, однако сортировка выбором требует меньше операций записи, и поэтому используется, когда производительность записи является ограничивающим фактором.

Сортировка вставки

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

Сортировка выбора

Сортировка выбором — это сортировка сравнением на месте. Она имеет сложность O(n²), что делает её неэффективной для больших списков и, как правило, работает хуже, чем аналогичная сортировка вставками. Сортировка выбором отличается простотой, а также может быть более эффективной, чем более сложные алгоритмы, в определенных ситуациях. Алгоритм находит минимальное значение, меняет его местами со значением в первой позиции и повторяет эти шаги для остальной части списка. Он выполняет не более n обменов, и поэтому полезна в тех случаях, когда обмен данных — дорогостоящая операция.

Эффективные сорта

Практические алгоритмы общей сортировки почти всегда основаны на алгоритме со средней временной сложностью (и, как правило, сложностью в худшем случае) O(n log n), среди которых наиболее распространены сортировка кучей, сортировка слиянием и быстрая сортировка. Каждый из них имеет свои преимущества и недостатки, причём наиболее значимым является то, что простая реализация сортировки слиянием использует O(n) дополнительной памяти, а простая реализация быстрой сортировки имеет сложность в худшем случае O(n²). Эти проблемы можно решить или смягчить за счёт более сложного алгоритма. Хотя эти алгоритмы асимптотически эффективны для случайных данных, для практической эффективности при работе с реальными данными используются различные модификации. Во-первых, накладные расходы этих алгоритмов становятся существенными для небольших объёмов данных, поэтому часто применяется гибридный алгоритм, обычно переключающийся на сортировку вставками, когда объём данных становится достаточно малым. Во-вторых, алгоритмы часто показывают плохие результаты на уже отсортированных или почти отсортированных данных – такие данные часто встречаются в реальных задачах и могут быть отсортированы за время O(n) с помощью подходящих алгоритмов. Наконец, они также могут быть неустойчивыми, а устойчивость часто является желательным свойством сортировки. Поэтому часто используются более сложные алгоритмы, такие как Timsort (основанный на сортировке слиянием) или introsort (основанный на быстрой сортировке, с переходом к сортировке кучей).

Слияние сортировки

Сортировка слиянием использует простоту объединения уже отсортированных списков в новый отсортированный список. Она начинается со сравнения каждой пары элементов (например, 1 с 2, затем 3 с 4) и их перестановки, если первый элемент должен идти после второго. Затем она объединяет каждый из полученных списков из двух элементов в списки из четырех, затем объединяет эти списки из четырех и так далее, пока, наконец, два списка не будут объединены в окончательный отсортированный список. Из описанных здесь алгоритмов, это первый, который хорошо масштабируется для работы с очень большими списками, поскольку его наихудшее время выполнения составляет O(n log n). Он также легко применим к спискам, а не только к массивам, так как требует только последовательного доступа, а не произвольного доступа. Однако он имеет дополнительную пространственную сложность O(n) и включает в себя большое количество операций копирования в простых реализациях. Сортировка слиянием в последнее время приобрела популярность для практических реализаций благодаря использованию в сложном алгоритме Timsort, который используется для стандартной процедуры сортировки в языках программирования Python и Java (по состоянию на JDK7). Сам алгоритм сортировки слиянием является стандартной процедурой в Perl и используется в Java как минимум с 2000 года, начиная с JDK1.3.

Сбор кучи

Heapsort — гораздо более эффективная версия сортировки выбором. Он также работает, определяя наибольший (или наименьший) элемент списка, помещая его в конец (или начало) списка, а затем продолжая работу с оставшейся частью списка, но выполняет эту задачу эффективно, используя структуру данных, называемую кучей — специальный тип двоичного дерева. Как только список данных преобразован в кучу, корневой узел гарантированно является наибольшим (или наименьшим) элементом. Когда он удаляется и помещается в конец списка, куча перестраивается таким образом, чтобы наибольший оставшийся элемент переместился к корню. Использование кучи позволяет находить следующий наибольший элемент за время O(log n), вместо O(n) при линейном просмотре, как в простой сортировке выбором. Это позволяет Heapsort выполняться за время O(n log n), и это также сложность в наихудшем случае.

Быстрый сортировщик

Quicksort — это алгоритм «разделяй и властвуй», основанный на операции разбиения: для разбиения массива выбирается элемент, называемый опорным. Все элементы, меньшие опорного, перемещаются перед ним, а все большие — после него. Это можно сделать эффективно за линейное время и на месте. Затем меньшие и большие подсписки рекурсивно сортируются. Это обеспечивает среднюю временную сложность O(n log n) с небольшими накладными расходами, что делает этот алгоритм популярным. Эффективные реализации быстрой сортировки (с разбиением на месте) обычно являются неустойчивыми и несколько сложными, но на практике являются одними из самых быстрых алгоритмов сортировки. В сочетании со скромным использованием памяти O(log n), быстрая сортировка является одним из самых популярных алгоритмов сортировки и доступна во многих стандартных библиотеках программирования. Важное замечание о быстрой сортировке заключается в том, что её наихудшая производительность составляет O(n²); хотя это случается редко, в наивных реализациях (при выборе первого или последнего элемента в качестве опорного) это происходит для отсортированных данных, что является распространённым случаем. Таким образом, наиболее сложной задачей в быстрой сортировке является выбор хорошего опорного элемента, поскольку последовательно плохой выбор может привести к значительно более медленной производительности O(n²), а хороший выбор обеспечивает производительность O(n log n), которая является асимптотически оптимальной. Например, если на каждом шаге в качестве опорного выбирается медиана, то алгоритм работает за O(n log n). Однако поиск медианы, например, с помощью алгоритма выбора медианы медиан, является операцией O(n) для несортированных списков и, следовательно, требует значительных накладных расходов при сортировке. На практике выбор случайного опорного элемента почти наверняка обеспечивает производительность O(n log n). Если важна гарантия производительности O(n log n), существует простое изменение для её достижения. Идея, предложенная Муссером, заключается в установке ограничения на максимальную глубину рекурсии. Если этот предел превышен, сортировка продолжается с использованием алгоритма сортировки кучей (heapsort). Муссер предложил, чтобы предел был равен 2 * log₂(n), что примерно в два раза больше максимальной глубины рекурсии, которую можно ожидать в среднем для случайно упорядоченного массива.

Раствор

Shellsort был изобретен Дональдом Шеллом в 1959 году. Он улучшает сортировку вставками, перемещая элементы, находящиеся не на своих местах, более чем на одну позицию за раз. Идея Shellsort заключается в том, что сортировка вставками работает за время O(kn), где k – максимальное расстояние между двумя элементами, которые не отсортированы по порядку. Это означает, что в общем случае она работает за O(n²), но для данных, которые почти отсортированы, с небольшим количеством элементов не на своих местах, она работает быстрее. Таким образом, сначала сортируя элементы, находящиеся далеко друг от друга, и постепенно уменьшая расстояние между сортируемыми элементами, финальная сортировка выполняется значительно быстрее. Один из способов реализации можно описать как организацию последовательности данных в двумерный массив, а затем сортировку столбцов этого массива с использованием сортировки вставками. Временная сложность Shellsort в худшем случае остаётся открытой проблемой и зависит от используемой последовательности шагов, при этом известные сложности варьируются от O(n²) до O(n⁴/₃) и Θ(n log₂ n). Это, в сочетании с тем фактом, что Shellsort выполняется "на месте", требует относительно небольшого количества кода и не использует стек вызовов, делает его полезным в ситуациях, когда память ограничена, например, во встроенных системах и ядрах операционных систем.

Сортировка пузырьков и варианты

Сортировка пузырьком и её варианты, такие как сортировка гребнем и шейкерная сортировка, — это простые, но крайне неэффективные алгоритмы сортировки. Они часто встречаются в учебных пособиях для начинающих благодаря простоте анализа, но редко применяются на практике.

Сортировка пузырьков

Сортировка пузырьком — это простой алгоритм сортировки. Алгоритм начинается с начала набора данных. Он сравнивает первые два элемента, и если первый больше второго, он меняет их местами. Он продолжает выполнять это для каждой пары соседних элементов до конца набора данных. Затем он снова начинает с первых двух элементов, повторяя процесс до тех пор, пока на последнем проходе не будет выполнено ни одной перестановки. Среднее и наихудшее время работы этого алгоритма составляет O(n²), поэтому он редко используется для сортировки больших, неупорядоченных наборов данных. Сортировку пузырьком можно использовать для сортировки небольшого количества элементов (когда её асимптотическая неэффективность не является существенным недостатком). Сортировка пузырьком также может эффективно использоваться для списков любой длины, которые почти отсортированы (то есть элементы не сильно отличаются от своего правильного положения). Например, если какое-либо количество элементов сдвинуто всего на одну позицию (например, 0123546789 и 1032547698), сортировка пузырьком упорядочит их за один проход, а второй проход покажет, что все элементы уже в порядке, поэтому сортировка займет всего 2n операций.

Сортировка гребня

Сортировка гребнем — относительно простой алгоритм сортировки, основанный на сортировке пузырьком и первоначально разработанный Влодзимежем Добосевичем в 1980 году. Позже он был повторно открыт и популяризирован Стивеном Лейси и Ричардом Боксом в статье, опубликованной в журнале Byte Magazine в апреле 1991 года. Основная идея заключается в устранении «черепах», то есть небольших значений в конце списка, поскольку в сортировке пузырьком они значительно замедляют процесс. («Кролики», то есть большие значения в начале списка, не создают проблем при сортировке пузырьком.) Это достигается путем первоначального обмена элементов, находящихся на определенном расстоянии друг от друга в массиве, а не только соседних элементов, с последующим уменьшением выбранного расстояния до тех пор, пока алгоритм не станет работать как обычная сортировка пузырьком. Таким образом, если сортировку Шеллсорта можно рассматривать как обобщенную версию сортировки вставками, которая обменивает элементы, расположенные на определенном расстоянии друг от друга, то сортировку гребнем можно рассматривать как то же обобщение, примененное к сортировке пузырьком.

Сортировка по обмену

Иногда сортировку обменом путают с сортировкой пузырьком, хотя эти алгоритмы на самом деле различны. Сортировка обменом работает путем сравнения первого элемента со всеми последующими элементами, выполняя обмен при необходимости, тем самым гарантируя, что первый элемент будет находиться на своем месте в окончательном отсортированном порядке; затем она повторяет эту процедуру для второго элемента и так далее. В отличие от сортировки пузырьком, она не может определить за один проход, отсортирован ли список, но в худшем случае может быть быстрее сортировки пузырьком на постоянный множитель (на один проход меньше по сортируемым данным; общее количество сравнений уменьшается вдвое). Как и любой простой алгоритм сортировки со сложностью O(n²), она может быть достаточно быстрой для очень маленьких наборов данных, хотя в большинстве случаев сортировка вставками будет работать быстрее.

Виды распространения

Распределенная сортировка — это любой алгоритм сортировки, при котором данные распределяются из входных данных в несколько промежуточных структур, которые затем собираются и помещаются в выходные данные. Например, сортировка подсчётом и Flashsort являются алгоритмами сортировки, основанными на распределении. Алгоритмы распределенной сортировки могут использоваться на одном процессоре или быть распределёнными алгоритмами, где отдельные подмножества сортируются независимо на разных процессорах, а затем объединяются. Это позволяет выполнять внешнюю сортировку данных, которые слишком велики для размещения в памяти одного компьютера.

Счетная сортировка

Счетная сортировка применима, когда известно, что каждый элемент входных данных принадлежит к определенному набору, S, возможных значений. Алгоритм выполняется за время O(|S| + n) и использует O(|S|) памяти, где n – длина входных данных. Он работает путем создания целочисленного массива размером |S| и использования i-го отсека (bin) для подсчета количества вхождений i-го элемента S во входных данных. Затем каждое входное значение подсчитывается путем увеличения значения соответствующего отсека. После этого счетный массив просматривается для упорядочивания всех входных данных. Этот алгоритм сортировки часто нельзя использовать, поскольку S должен быть достаточно малым для обеспечения эффективности алгоритма, но он чрезвычайно быстр и демонстрирует хорошее асимптотическое поведение при увеличении n. Его также можно модифицировать для обеспечения стабильной сортировки.

Сортировка по коврам

Сортировка корзинами — это алгоритм сортировки, основанный на принципе "разделяй и властвуй", который является обобщением сортировки подсчётом. Он разделяет массив на конечное число корзин. Затем каждая корзина сортируется отдельно, либо с использованием другого алгоритма сортировки, либо рекурсивным применением сортировки корзинами. Сортировка корзинами наиболее эффективна, когда элементы набора данных равномерно распределены по всем корзинам.

Сортировка радикса

Радикс-сортировка — это алгоритм, который сортирует числа, обрабатывая отдельные цифры. n чисел, состоящих из k цифр, сортируются за время O(n · k). Радикс-сортировка может обрабатывать цифры каждого числа, начиная с наименее значимой цифры (LSD) или с наиболее значимой цифры (MSD). Алгоритм LSD сначала сортирует список по наименее значимой цифре, сохраняя при этом их относительный порядок с помощью стабильной сортировки. Затем он сортирует их по следующей цифре и так далее от наименее значимой к наиболее значимой, в итоге получая отсортированный список. В то время как LSD-радикс-сортировка требует использования стабильной сортировки, алгоритм MSD-радикс-сортировки не требует этого (если только не требуется стабильная сортировка). MSD-радикс-сортировка на месте не является стабильной. Часто внутри радикс-сортировки используется алгоритм сортировки подсчётом. Гибридный подход к сортировке, например, использование сортировки вставками для небольших групп, значительно повышает производительность радикс-сортировки.

Схемы использования памяти и сортировка индексов

Когда размер массива, подлежащего сортировке, приближается к объему доступной оперативной памяти или превышает его, что приводит к использованию (значительно более медленной) дисковой памяти или файла подкачки, схема использования памяти алгоритмом сортировки становится важной. Алгоритм, который мог быть достаточно эффективным, когда массив легко помещался в оперативную память, может оказаться непрактичным. В этом сценарии общее количество сравнений становится (относительно) менее значимым, а количество операций копирования или перемещения блоков памяти на диск и обратно может стать определяющим фактором производительности алгоритма. Таким образом, количество проходов и локальность сравнений могут быть более важными, чем простое количество сравнений, поскольку сравнение соседних элементов происходит на скорости системной шины (или, при использовании кэша, даже на скорости процессора), что, по сравнению со скоростью диска, практически мгновенно. Например, популярный рекурсивный алгоритм быстрой сортировки демонстрирует вполне приемлемую производительность при достаточном объеме оперативной памяти, но из-за рекурсивного копирования частей массива он становится гораздо менее эффективным, когда массив не помещается в оперативную память, поскольку это может привести к множеству медленных операций копирования или перемещения данных на диск и обратно. В этом случае предпочтительнее использовать другой алгоритм, даже если он требует большего общего количества сравнений. Один из способов решения этой проблемы, который хорошо работает при сортировке сложных записей (например, в реляционной базе данных) по относительно небольшому ключевому полю, заключается в создании индекса для массива и последующей сортировке индекса, а не всего массива. (Отсортированная версия всего массива затем может быть получена за один проход, считывая данные из индекса, но часто даже это не требуется, поскольку достаточно иметь отсортированный индекс.) Поскольку индекс значительно меньше всего массива, он может легко поместиться в оперативную память, где весь массив не поместится, эффективно устраняя проблему обмена данными с диском. Эта процедура иногда называется "сортировка по меткам". Другой способ решения проблемы с объемом памяти – использование внешней сортировки, например, путем комбинирования двух алгоритмов таким образом, чтобы использовать сильные стороны каждого из них для повышения общей производительности. Например, массив можно разделить на блоки, размер которых позволяет им поместиться в оперативную память, содержимое каждого блока отсортировать с помощью эффективного алгоритма (например, быстрой сортировки), а затем объединить результаты с помощью k-путевого слияния, аналогичного используемому в сортировке слиянием. Это быстрее, чем выполнение сортировки слиянием или быстрой сортировки для всего списка. Можно также комбинировать различные методы. Для сортировки очень больших наборов данных, значительно превышающих объем системной памяти, даже индекс может потребовать сортировки с использованием алгоритма или комбинации алгоритмов, предназначенных для эффективной работы с виртуальной памятью, то есть для уменьшения количества операций обмена.

Связанные алгоритмы

Сюда относятся приближенная сортировка (сортировка последовательности с допустимым отклонением от правильного порядка), частичная сортировка (сортировка только k наименьших элементов списка или поиск k наименьших элементов без упорядочивания) и отбор (вычисление k-го наименьшего элемента). Эти задачи можно решить неэффективно с помощью полной сортировки, но существуют более эффективные алгоритмы, часто получаемые обобщением алгоритма сортировки. Наиболее заметным примером является quickselect, который связан с quicksort. И наоборот, некоторые алгоритмы сортировки могут быть получены путем повторного применения алгоритма отбора; quicksort и quickselect можно рассматривать как один и тот же шаг разделения, отличающийся лишь тем, рекурсивно применяется он к обеим частям (quicksort, метод «разделяй и властвуй») или к одной части (quickselect, метод «уменьшай и властвуй»). Противоположностью алгоритма сортировки является алгоритм перемешивания. Они принципиально различны, поскольку требуют источника случайных чисел. Перемешивание также можно реализовать с помощью алгоритма сортировки, а именно случайной сортировки: присвоение случайного числа каждому элементу списка и последующая сортировка на основе этих чисел. Однако на практике это обычно не делается, и существует хорошо известный простой и эффективный алгоритм перемешивания: алгоритм Фишера — Йейтса. Алгоритмы сортировки неэффективны для установления порядка во многих ситуациях. Обычно это происходит, когда элементы не имеют надежной функции сравнения (например, предпочтения, полученные из коллективных источников, такие как системы голосования), сравнения очень затратны (например, в спорте) или когда невозможно попарно сравнить все элементы по всем критериям (например, в поисковых системах). В этих случаях задача обычно называется ранжированием, и цель состоит в том, чтобы найти "лучший" результат по заданным критериям на основе вероятностей, полученных из сравнений или ранжирования. Типичным примером является шахматы, где игроки ранжируются с помощью системы рейтинга Эло, а ранги определяются турнирной системой, а не алгоритмом сортировки.