Быстрая сортировка: алгоритм «разделяй и властвуй»

Введение

Алгоритм сортировки по принципу "разделяй и властвуй"

Quicksort — эффективный алгоритм сортировки общего назначения. Quicksort был разработан британским учёным-компьютерщиком Тони Хоаром в 1959 году и опубликован в 1961 году. Он до сих пор является широко используемым алгоритмом сортировки. В целом, он немного быстрее, чем сортировка слиянием и сортировка кучей для случайных данных, особенно для больших наборов данных. Quicksort — это алгоритм "разделяй и властвуй". Он работает путём выбора "опорного" элемента из массива и разделения остальных элементов на два подмассива в зависимости от того, меньше они или больше опорного элемента. По этой причине он иногда называется сортировкой обменом с разделением. Затем подмассивы сортируются рекурсивно. Это можно выполнить на месте, требуя небольшого дополнительного объёма памяти для выполнения сортировки. Quicksort — это алгоритм сортировки сравнением, то есть он может сортировать элементы любого типа, для которых определено отношение "меньше" (формально, полный порядок). Это алгоритм сортировки, основанный на сравнении, поскольку элементы a и b меняются местами только в том случае, если их относительный порядок был определён в транзитивном замыкании предыдущих результатов сравнения. Большинство реализаций Quicksort не являются стабильными, то есть относительный порядок равных элементов не сохраняется. Математический анализ Quicksort показывает, что в среднем алгоритм выполняет сравнений для сортировки n элементов. В худшем случае он выполняет сравнений.

История

Алгоритм быстрой сортировки был разработан в 1959 году Тони Хоаром, когда он был студентом-гостем в Московском государственном университете. В то время Хоар работал над проектом машинного перевода для Национальной физической лаборатории. В процессе перевода ему требовалось сортировать слова в русских предложениях, прежде чем искать их в русско-английском словаре, который был упорядочен по алфавиту на магнитной ленте. Поняв, что его первоначальная идея – сортировка вставками – будет работать медленно, он придумал новый подход. Он написал часть, отвечающую за разделение, на языке Mercury Autocode, но столкнулся с трудностями при работе со списком неотсортированных сегментов. По возвращении в Англию его попросили написать код для Shellsort. Хоар упомянул своему начальнику, что знает более быстрый алгоритм, и тот заключил с ним пари в шесть пенсов, что это не так. В итоге начальник признал, что проиграл пари. Хоар опубликовал статью о своем алгоритме в журнале The Computer Journal, том 5, выпуск 1, 1962, страницы 10–16. Позже Хоар узнал о языке ALGOL и его возможности рекурсии, что позволило ему опубликовать улучшенную версию алгоритма на ALGOL в Communications of the Association for Computing Machinery, ведущем журнале в области компьютерных наук того времени. Код на ALGOL был опубликован в Communications of the ACM (CACM), том 4, выпуск 7, июль 1961 года, страницы 321, как Алгоритм 63: разделение и Алгоритм 64: быстрая сортировка. Быстрая сортировка получила широкое распространение, например, в Unix она использовалась в качестве подпрограммы сортировки по умолчанию в библиотеке. Благодаря этому она дала название подпрограмме стандартной библиотеки C, а также методам вычисления ожидаемого количества сравнений и обменов. Бентли описал Quicksort как "самый красивый код, который я когда-либо писал" в том же эссе. Схема разделения Ломуто также стала популярной благодаря учебнику "Введение в алгоритмы", хотя она уступает схеме Хоара, поскольку в среднем выполняет в три раза больше обменов и деградирует до времени выполнения O(n²) в случае, когда все элементы равны. МакИлрой позже создал функцию AntiQuicksort в 1998 году, которая последовательно переводит даже его вариант Quicksort 1993 года в квадратичное поведение, генерируя на лету данные, специально предназначенные для ухудшения производительности.

The quicksort algorithm was developed in 1959 by Tony Hoare while he was a visiting student at Moscow State University. At that time, Hoare was working on a machine translation project for the National Physical Laboratory. As a part of the translation process, he needed to sort the words in Russian sentences before looking them up in a Russian English dictionary, which was in alphabetical order on magnetic tape. After recognizing that his first idea, insertion sort, would be slow, he came up with a new idea. He wrote the partition part in Mercury Autocode but had trouble dealing with the list of unsorted segments. On return to England, he was asked to write code for Shellsort. Hoare mentioned to his boss that he knew of a faster algorithm and his boss bet a sixpence that he did not. His boss ultimately accepted that he had lost the bet. Hoare published a paper about his algorithm in The Computer Journal Volume 5, Issue 1, 1962, Pages 10–16. Later, Hoare learned about ALGOL and its ability to do recursion that enabled him to publish an improved version of the algorithm in ALGOL in Communications of the Association for Computing Machinery, the premier computer science journal of the time. The ALGOL code is published in Communications of the ACM (CACM), Volume 4, Issue 7 July 1961, pp 321 Algorithm 63: partition and Algorithm 64: Quicksort. Quicksort gained widespread adoption, appearing, for example, in Unix as the default library sort subroutine. Hence, it lent its name to the C standard library subroutine as well as derivation of expected number of comparisons and swaps. Bentley described Quicksort as the "most beautiful code I had ever written" in the same essay. Lomuto's partition scheme was also popularized by the textbook Introduction to Algorithms although it is inferior to Hoare's scheme because it does three times more swaps on average and degrades to O(n^(2)) runtime when all elements are equal. McIlroy would further produce an AntiQuicksort function in 1998, which consistently drives even his 1993 variant of Quicksort into quadratic behavior by producing adversarial data on the fly.

Алгоритм

Quicksort — это тип алгоритма «разделяй и властвуй» для сортировки массива, основанный на процедуре разделения; детали этой процедуры могут несколько варьироваться, поэтому quicksort представляет собой семейство тесно связанных алгоритмов. Применяемый к диапазону, содержащему как минимум два элемента, процесс разделения создает разделение на два последовательных непустых поддиапазона таким образом, чтобы ни один элемент первого поддиапазона не был больше любого элемента второго поддиапазона. После применения этого разделения quicksort рекурсивно сортирует поддиапазоны, возможно, исключив из них элемент в точке разделения, который к этому моменту уже находится в окончательной позиции. В силу своей рекурсивной природы quicksort (как и процедура разделения) должен быть сформулирован таким образом, чтобы его можно было вызывать для диапазона внутри большего массива, даже если конечная цель — сортировка всего массива. Шаги для quicksort на месте следующие:
Если диапазон содержит менее двух элементов, немедленно возвращайтесь, так как выполнять нечего. Возможно, для других очень коротких диапазонов применяется специализированный метод сортировки, и остальные шаги пропускаются. В противном случае выберите значение, называемое опорным элементом (pivot), которое присутствует в диапазоне (точный способ выбора зависит от процедуры разделения и может включать в себя случайность). Разделите диапазон: переупорядочите его элементы, определяя точку разделения, так чтобы все элементы со значениями меньше опорного элемента оказались перед точкой разделения, а все элементы со значениями больше опорного элемента — после нее; элементы, равные опорному элементу, могут располагаться в любом порядке. Поскольку в диапазоне присутствует как минимум один опорный элемент, большинство процедур разделения гарантируют, что значение, которое окажется в точке разделения, равно опорному элементу и теперь находится в окончательной позиции (однако завершение quicksort не зависит от этого, пока генерируются поддиапазоны, строго меньшие исходного). Рекурсивно примените quicksort к поддиапазону до точки разделения и к поддиапазону после нее, возможно, исключив из обоих диапазонов элемент, равный опорному элементу в точке разделения. (Если разделение создает потенциально больший поддиапазон вблизи границы, где все элементы, как известно, равны опорному элементу, их также можно исключить.) Выбор процедуры разделения (включая выбор опорного элемента) и другие детали, не полностью указанные выше, могут повлиять на производительность алгоритма, возможно, в значительной степени для конкретных входных массивов. Поэтому при обсуждении эффективности quicksort необходимо сначала указать эти варианты. Здесь мы упомянем два конкретных метода разделения.

Quicksort is a type of divide and conquer algorithm for sorting an array, based on a partitioning routine; the details of this partitioning can vary somewhat, so that quicksort is really a family of closely related algorithms. Applied to a range of at least two elements, partitioning produces a division into two consecutive non empty sub ranges, in such a way that no element of the first sub range is greater than any element of the second sub range. After applying this partition, quicksort then recursively sorts the sub ranges, possibly after excluding from them an element at the point of division that is at this point known to be already in its final location. Due to its recursive nature, quicksort (like the partition routine) has to be formulated so as to be callable for a range within a larger array, even if the ultimate goal is to sort a complete array. The steps for in place quicksort are:
If the range has fewer than two elements, return immediately as there is nothing to do. Possibly for other very short lengths a special purpose sorting method is applied and the remainder of these steps skipped. Otherwise pick a value, called a pivot, that occurs in the range (the precise manner of choosing depends on the partition routine, and can involve randomness). Partition the range: reorder its elements, while determining a point of division, so that all elements with values less than the pivot come before the division, while all elements with values greater than the pivot come after it; elements that are equal to the pivot can go either way. Since at least one instance of the pivot is present, most partition routines ensure that the value that ends up at the point of division is equal to the pivot, and is now in its final position (but termination of quicksort does not depend on this, as long as sub ranges strictly smaller than the original are produced). Recursively apply the quicksort to the sub range up to the point of division and to the sub range after it, possibly excluding from both ranges the element equal to the pivot at the point of division. (If the partition produces a possibly larger sub range near the boundary where all elements are known to be equal to the pivot, these can be excluded as well.) The choice of partition routine (including the pivot selection) and other details not entirely specified above can affect the algorithm's performance, possibly to a great extent for specific input arrays. In discussing the efficiency of quicksort, it is therefore necessary to specify these choices first. Here we mention two specific partition methods.

Параллелизация

Формулировка "разделяй и властвуй" в алгоритме Quicksort делает его удобным для параллелизации с использованием параллелизма задач. Шаг разделения выполняется с помощью алгоритма параллельного вычисления префиксных сумм для вычисления индекса для каждого элемента массива в его секции отсортированного массива. Для массива размера n, шаг разделения выполняет O(n) операций за O(log n) времени и требует O(n) дополнительной памяти для временных данных. После разделения массива, два подмассива могут быть отсортированы рекурсивно параллельно. При оптимальном выборе опорного элемента, параллельный Quicksort сортирует массив размера n за O(n log n) операций за O(log² n) времени, используя O(n) дополнительной памяти. Quicksort имеет некоторые недостатки по сравнению с альтернативными алгоритмами сортировки, такими как сортировка слиянием, которые затрудняют его эффективную параллелизацию. Глубина дерева "разделяй и властвуй" Quicksort напрямую влияет на масштабируемость алгоритма, и эта глубина сильно зависит от выбора опорного элемента. Кроме того, сложно эффективно параллелизовать шаг разделения на месте. Использование временной памяти упрощает шаг разделения, но увеличивает объем памяти, используемый алгоритмом, и постоянные накладные расходы. Другие, более сложные алгоритмы параллельной сортировки могут достигать еще лучших временных ограничений. Например, в 1991 году Дэвид М. У. Пауэрс описал параллелизированный Quicksort (и связанную с ним поразрядную сортировку), который может работать за O(log n) времени на CRCW (concurrent read, concurrent write) PRAM (parallel random access machine) с n процессорами, выполняя разделение неявно.

Анализ наихудшего сценария

Наиболее несбалансированный раздел происходит, когда один из подсписков, возвращаемых процедурой разделения, имеет размер n − 1. Это может произойти, если опорный элемент оказывается наименьшим или наибольшим в списке, или в некоторых реализациях (например, схема разделения Lomuto, как описано выше), когда все элементы равны. Если это происходит неоднократно на каждом шаге разделения, то каждый рекурсивный вызов обрабатывает список на один элемент меньше предыдущего. Следовательно, можно сделать n − 1 вложенных вызовов, прежде чем достигнуть списка размера 1. Это означает, что дерево вызовов представляет собой линейную цепочку из n − 1 вложенных вызовов. i-й вызов выполняет O(n − i) операций для разделения, и, следовательно, в этом случае быстрая сортировка занимает O(n^(2)) времени.

Анализ наилучшего сценария

В наиболее сбалансированном случае, при каждом разбиении список делится на две почти равные части. Это означает, что каждый рекурсивный вызов обрабатывает список вдвое меньшего размера. Следовательно, мы можем сделать не более чем log2 n вложенных вызовов, прежде чем достигнем списка размером 1. Таким образом, глубина дерева вызовов равна log2 n. Однако, никакие два вызова на одном уровне дерева вызовов не обрабатывают одну и ту же часть исходного списка; следовательно, для обработки каждого уровня вызовов требуется только O(n) времени (каждый вызов имеет некоторую постоянную накладную, но поскольку на каждом уровне выполняется только O(n) вызовов, эта накладная учитывается в факторе O(n)). В результате алгоритм использует только O(n log n) времени.

Анализ среднего случая

Для сортировки массива из n различных элементов, быстрая сортировка требует O(n log n) времени в среднем, усредненное по всем n! перестановкам n элементов с равной вероятностью. В качестве альтернативы, если алгоритм выбирает опорный элемент (pivot) равномерно случайным образом из входного массива, тот же анализ может быть использован для оценки ожидаемого времени выполнения для любой входной последовательности; при этом ожидание берется по случайным выборам, сделанным алгоритмом (Cormen et al., Введение в алгоритмы).

Быстрая сортировка с разделением на месте и нестабильным разделением использует только постоянный объем дополнительной памяти перед любым рекурсивным вызовом. Быстрой сортировке необходимо хранить постоянное количество информации для каждого вложенного рекурсивного вызова. Поскольку в лучшем случае выполняется не более O(log n) вложенных рекурсивных вызовов, она использует O(log n) памяти. Однако, без приема Седжвика для ограничения рекурсивных вызовов, в худшем случае быстрая сортировка может выполнить O(n) вложенных рекурсивных вызовов и потребовать O(n) дополнительной памяти. С точки зрения битовой сложности, переменные, такие как lo и hi, не используют постоянный объем памяти; для индексации в список из n элементов требуется O(log n) бит. Поскольку такие переменные присутствуют в каждом фрейме стека, быстрая сортировка с использованием приема Седжвика требует O((log n)^2) бит памяти. Это требование к памяти не является критичным, поскольку если список содержал различные элементы, ему потребовалось бы не менее O(n log n) бит памяти. Другая, менее распространенная, версия быстрой сортировки, не выполняющаяся на месте, использует O(n) памяти для рабочего хранилища и может реализовать стабильную сортировку. Рабочее хранилище позволяет легко разделить входной массив стабильным образом, а затем скопировать его обратно во входной массив для последующих рекурсивных вызовов. Оптимизация Седжвика по-прежнему применима.

Связь с другими алгоритмами

Quicksort – это пространственно оптимизированная версия сортировки бинарным деревом. Вместо последовательного добавления элементов в явное дерево, быстрая сортировка организует их одновременно в дерево, которое подразумевается рекурсивными вызовами. Алгоритмы выполняют ровно те же сравнения, но в другом порядке. Часто желаемым свойством алгоритма сортировки является стабильность – то есть порядок элементов, которые сравниваются как равные, не изменяется, что позволяет естественным образом контролировать порядок таблиц с несколькими ключами (например, списков каталогов или папок). Это свойство сложно поддерживать для быстрой сортировки на месте (которая использует только постоянный объем дополнительной памяти для указателей и буферов и O(log n) дополнительной памяти для управления явной или неявной рекурсией). Для вариантов быстрой сортировки, требующих дополнительную память из-за представлений с использованием указателей (например, списков или деревьев) или файлов (фактически списков), обеспечение стабильности тривиально. Более сложные или диско-ориентированные структуры данных, как правило, увеличивают временные затраты, в целом увеличивая использование виртуальной памяти или диска. Прямым конкурентом быстрой сортировки является сортировка кучей (heapsort). Сортировка кучей обладает преимуществами простоты и гарантированного времени выполнения в худшем случае O(n log n), но среднее время выполнения сортировки кучей обычно считается медленнее, чем у быстрой сортировки на месте, главным образом из-за худшей локальности ссылок. Этот результат является спорным; некоторые публикации указывают на обратное. Основным недостатком быстрой сортировки является сложность реализации, необходимая для избежания неудачного выбора опорного элемента и, как следствие, снижения производительности. Introsort – это вариант быстрой сортировки, который решает эту проблему, переключаясь на сортировку кучей при обнаружении неблагоприятного сценария. Основные языки программирования, такие как C++ (в реализациях GNU и LLVM), используют introsort. Оценка 1999 года многоключевой быстрой сортировки с переменным числом опорных элементов, настроенной для эффективного использования кэшей процессора, показала увеличение количества инструкций примерно на 20%, но результаты моделирования показали, что она может быть более эффективной при очень больших объемах данных. Версия быстрой сортировки с двойным опорным элементом, разработанная Ярославским в 2009 году, оказалась достаточно быстрой, чтобы быть реализованной в Java 7 в качестве стандартного алгоритма сортировки массивов примитивных типов (сортировка массивов объектов выполняется с использованием Timsort). Впоследствии было установлено, что выигрыш в производительности этого алгоритма в основном связан с производительностью кэша, и экспериментальные результаты показывают, что вариант с тремя опорными элементами может работать еще лучше на современных машинах.

Quicksort is a space optimized version of the binary tree sort. Instead of inserting items sequentially into an explicit tree, quicksort organizes them concurrently into a tree that is implied by the recursive calls. The algorithms make exactly the same comparisons, but in a different order. An often desirable property of a sorting algorithm is stability – that is the order of elements that compare equal is not changed, allowing controlling order of multikey tables (e. g. directory or folder listings) in a natural way. This property is hard to maintain for in place quicksort (that uses only constant additional space for pointers and buffers, and O(log n) additional space for the management of explicit or implicit recursion). For variant quicksorts involving extra memory due to representations using pointers (e. g. lists or trees) or files (effectively lists), it is trivial to maintain stability. The more complex, or disk bound, data structures tend to increase time cost, in general making increasing use of virtual memory or disk. The most direct competitor of quicksort is heapsort. Heapsort has the advantages of simplicity, and a worst case run time of O(n log n), but heapsort's average running time is usually considered slower than in place quicksort, primarily due to its worse locality of reference. This result is debatable; some publications indicate the opposite. The main disadvantage of quicksort is the implementation complexity required to avoid bad pivot choices and the resultant performance. Introsort is a variant of quicksort which solves this problem by switching to heapsort when a bad case is detected. Major programming languages, such as C++ (in the GNU and LLVM implementations), use introsort. A 1999 assessment of a multiquicksort with a variable number of pivots, tuned to make efficient use of processor caches, found it to increase the instruction count by some 20%, but simulation results suggested that it would be more efficient on very large inputs. A version of dual pivot quicksort developed by Yaroslavskiy in 2009 turned out to be fast enough to warrant implementation in Java 7, as the standard algorithm to sort arrays of primitives (sorting arrays of objects is done using Timsort). The performance benefit of this algorithm was subsequently found to be mostly related to cache performance, and experimental results indicate that the three pivot variant may perform even better on modern machines.

Внешний быстрый сортировщик

Для дисковых файлов возможна внешняя сортировка, основанная на разделении, аналогичная быстрой сортировке. Она медленнее внешней сортировки слиянием, но не требует дополнительного дискового пространства. Используются 4 буфера: 2 для ввода и 2 для вывода. Пусть N – количество записей в файле, B – количество записей в буфере, а M = N/B – количество буферных сегментов в файле. Данные читаются (и записываются) с обоих концов файла внутрь. Пусть X обозначает сегменты, начинающиеся в начале файла, а Y – сегменты, начинающиеся в конце файла. Данные считываются в буферы чтения X и Y. Выбирается опорная запись, и записи в буферах X и Y, отличные от опорной, копируются в буфер записи X в возрастающем порядке и в буфер записи Y в убывающем порядке на основе сравнения с опорной записью. Как только буфер X или Y заполняется, он записывается в файл, а следующий буфер X или Y считывается из файла. Процесс продолжается до тех пор, пока все сегменты не будут прочитаны, и не останется один буфер записи. Если этот буфер – буфер записи X, то опорная запись добавляется в конец, и буфер X записывается. Если этот буфер – буфер записи Y, то опорная запись добавляется в начало, и буфер Y записывается. Это составляет один шаг разделения файла, и файл теперь состоит из двух подфайлов. Начальные и конечные позиции каждого подфайла помещаются в стек (push) или извлекаются из стека (pop) с использованием рекурсии, либо в отдельный стек, либо в основной стек. Чтобы ограничить объем памяти, используемой стеком, до O(log2(n)), сначала обрабатывается меньший подфайл. Для отдельного стека параметры большего подфайла помещаются в стек, затем выполняется итерация по меньшему подфайлу. Для рекурсии сначала выполняется рекурсивный вызов для меньшего подфайла, а затем итерация для обработки большего подфайла. Как только подфайл содержит не более 4B записей, он сортируется на месте с помощью быстрой сортировки и записывается. Этот подфайл теперь отсортирован и находится на месте в файле. Процесс продолжается до тех пор, пока все подфайлы не будут отсортированы и находиться на месте. Среднее количество проходов по файлу составляет приблизительно 1 + ln(N+1)/(4B), но в худшем случае – N проходов (что эквивалентно O(n^2) для худшего случая внутренней сортировки).

For disk files, an external sort based on partitioning similar to quicksort is possible. It is slower than external merge sort, but doesn't require extra disk space. 4 buffers are used, 2 for input, 2 for output. Let N = number of records in the file, B = the number of records per buffer, and M = N/B = the number of buffer segments in the file. Data is read (and written) from both ends of the file inwards. Let X represent the segments that start at the beginning of the file and Y represent segments that start at the end of the file. Data is read into the X and Y read buffers. A pivot record is chosen and the records in the X and Y buffers other than the pivot record are copied to the X write buffer in ascending order and Y write buffer in descending order based comparison with the pivot record. Once either X or Y buffer is filled, it is written to the file and the next X or Y buffer is read from the file. The process continues until all segments are read and one write buffer remains. If that buffer is an X write buffer, the pivot record is appended to it and the X buffer written. If that buffer is a Y write buffer, the pivot record is prepended to the Y buffer and the Y buffer written. This constitutes one partition step of the file, and the file is now composed of two subfiles. The start and end positions of each subfile are pushed/popped to a stand alone stack or the main stack via recursion. To limit stack space to O(log2(n)), the smaller subfile is processed first. For a stand alone stack, push the larger subfile parameters onto the stack, iterate on the smaller subfile. For recursion, recurse on the smaller subfile first, then iterate to handle the larger subfile. Once a sub file is less than or equal to 4 B records, the subfile is sorted in place via quicksort and written. That subfile is now sorted and in place in the file. The process is continued until all sub files are sorted and in place. The average number of passes on the file is approximately 1 + ln(N+1)/(4 B), but worst case pattern is N passes (equivalent to O(n^2) for worst case internal sort).

Трехсторонний быстрый сортировщик радиксов

Этот алгоритм является комбинацией поразрядной сортировки и быстрой сортировки. Выберите элемент из массива (опорный элемент) и рассмотрите первый символ (ключ) строки (многоключевой). Разделите оставшиеся элементы на три множества: те, чей соответствующий символ меньше, равен и больше символа опорного элемента. Рекурсивно отсортируйте разделы "меньше" и "больше" по тому же символу. Рекурсивно отсортируйте раздел "равно" по следующему символу (ключу). Если мы сортируем, используя байты или слова длиной W бит, то в лучшем случае сложность составит O(KN), а в худшем случае O(2^K * N) или, по крайней мере, O(N^2), как и для стандартной быстрой сортировки, при условии, что ключи уникальны и N < 2^K, где K – скрытая константа во всех стандартных алгоритмах сортировки сравнением, включая быструю сортировку. Это разновидность трехпутевой быстрой сортировки, в которой средний раздел представляет собой (тривиально) отсортированный подмассив элементов, точно равных опорному элементу.

Быстрая сортировка корней

Также разработанный Пауэрсом как параллельный алгоритм PRAM со сложностью O(K). Это снова комбинация поразрядной сортировки и быстрой сортировки, но решение о разделении на левую и правую части при быстрой сортировке принимается последовательно по битам ключа, что обеспечивает сложность O(KN) для N K-битовых ключей. Все алгоритмы сортировки сравнением неявно предполагают трансдихотомическую модель с K в Θ(log N), поскольку при меньшем K можно выполнить сортировку за время O(N) с использованием хеш-таблицы или сортировки целых чисел. Если K ≫ log N, но элементы уникальны в пределах O(log N) бит, оставшиеся биты не будут учитываться ни быстрой сортировкой, ни быстрой поразрядной сортировкой. В противном случае все алгоритмы сортировки сравнением также будут иметь одинаковые накладные расходы на просмотр O(K) относительно бесполезных бит, но быстрая поразрядная сортировка позволит избежать наихудшего случая O(N²) стандартной быстрой сортировки и быстрой поразрядной сортировки и будет быстрее даже в лучшем случае этих алгоритмов сравнения при условии уникальности префикса (K ≫ log N). Подробное обсуждение скрытых накладных расходов при сортировке сравнением, поразрядной сортировке и параллельной сортировке см. в работе Пауэрса.

Блок-быстрый сортировщик

В любом алгоритме сортировки, основанном на сравнении, минимизация числа сравнений требует максимизации объема информации, получаемой из каждого сравнения, то есть результаты сравнений должны быть непредсказуемыми. Это приводит к частым ошибкам предсказания переходов, что ограничивает производительность. BlockQuicksort реорганизует вычисления быстрой сортировки, чтобы преобразовать непредсказуемые ветвления в зависимости от данных. При разбиении входные данные делятся на блоки умеренного размера (которые легко помещаются в кэш данных), и два массива заполняются позициями элементов, подлежащих обмену. (Чтобы избежать условных переходов, позиция безусловно сохраняется в конце массива, а индекс конца увеличивается, если требуется обмен.) Второй проход выполняет обмен элементов в позициях, указанных в массивах. Обе петли содержат только одно условное ветвление – проверку завершения, которая обычно выполняется. Метод BlockQuicksort интегрирован в реализацию C++ STL в LLVM, libcxx, обеспечивая 50%-ное улучшение производительности при работе со случайными последовательностями целых чисел. Этот метод также используется в pdqsort – варианте алгоритма интроспективной сортировки.

Частичный и инкрементальный быстрый сортировщик

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

Обобщение

Ричард Коул и Дэвид К. Кандатил в 2004 году открыли однопараметрическое семейство алгоритмов сортировки, называемых алгоритмами сортировки разбиением, которые в среднем (при равновероятности всех возможных входных последовательностей) выполняют не более сравнений (близко к информационно-теоретической нижней границе) и операций; в худшем случае они выполняют сравнений (и также операций); эти алгоритмы выполняются "на месте", требуя лишь дополнительного пространства. Практическая эффективность и меньшая дисперсия производительности были продемонстрированы в сравнении с оптимизированными быстрыми сортировками (Sedgewick и Bentley McIlroy).