И ещё о сортировках

Рискну опять поднять эту тему. Начну со ссылки на статью Михаила Опанасенко (oms7), очень впечатляющую по объёмам проделанной работы, а также по количеству приведёных ссылок. Свой материал начал готовить, не зная об этой публикации, что впоследствии, после ознакомления привело к необходимости его существенной переработки. Для тех, кто уже прочитал эту статью, сообщаю, что в моём материале, исследуются более разнообразные по типам данные, в частности, строки и вещественные числа, используются библиотеки boost и bsd, а также затрагиваются некоторые другие отсутствующие в названной статье темы.

Существуют десятки различных способов расположить элементы данных по порядку. Среди них выделяют те, что работают быстро, такие, что, например, могут в максимум за минуты отсортировать любой массив данных, размещенный в оперативной памяти компьютера. Более конкретно можно сказать, что сортировка, работающая быстро, упорядочивает на хорошем современном персональном компьютере миллиард целых чисел за менее, чем сто секунд. Если использовать для сортировки большего числа элементов примитивные, небыстрые методы, например, пузырьковую сортировку или сортировку выбором, то время, затраченное на такую обработку данных может превзойти любые ожидания – такой «процессинг» реально может занять несколько дней, недель и даже лет. Эта большая разница вызвана тем, что время сортировки быстрыми методами занимает величину примерно пропорциональную Nlog N, а примитивными – N². С ростом N разница между двумя величинами становится очень заметной. Поэтому примитивные методы разумно использовать только для работ с данными небольшого объёма, например, на современных компьютерах до нескольких тысяч элементов. Их также естественно использовать для обучения азам программирования и логического мышления, так как они существенно проще, чем быстрые методы.

Хотелось бы разобраться в существующих в нынешних стандартных библиотеках методах сортировки. Выяснить как велика разница между ними по основной характеристике, скорости работы, а также их характерные особенности. Кроме того, рассмотрим попутно для сравнения и упражнения для ума некоторые несложные в реализации методы. Стоит ещё, отметить, что оптимизатор компилятора GCC и возможно других хороших компиляторов работает с сортировками очень хорошо, ускоряя код в несколько раз (иногда даже более 5 раз).

Начнём с метода пузырька (bubble sort) как самого простого и медленного. По этому методу нужно раз за разом проходить по массиву данных, сравнивая соседние элементы и меняя их местами, если порядок между ними нарушен. После каждого прохода, как минимум, один элемент (наибольший или наименьший – зависит от выбранного порядка) оказывается на своём месте. Помимо простоты у этого метода есть ещё одно достоинство, он не требует дополнительной памяти. Можно отметить ещё одну особенность метода пузырька – он очень быстро обрабатывает уже упорядоченные данные и это в отдельных случаях делает его одним из самых быстрых методов. Если данные только частично упорядочены, то этот метод работает с ними быстрее, но в большинстве случаев лишь совсем незначительно. Для тестов я использовал следующую реализацию.

Ещё один медленный метод – сортировка выбором (selection sort). Здесь на каждом проходе сначала находятся наибольший и наименьший элементы в данных и затем эти элементы ставятся в соответствующие выбранному порядку крайние позиции. На следующем проходе сортируем уже данные без этих крайних элементов. Этот метод так же прост, как и пузырьковая сортировка, и так же не требует дополнительной памяти, но он заметно быстрее. Более того, сортировка по этому методу выполняет рекордно минимальное количество перестановок элементов данных. Поэтому в случае, когда перестановки значительно медленнее сравнений, упорядочение методом выбора может оказаться приемлемым, если число элементов данных невелико. Вот моя реализация. Чаще такую сортировку реализуют, ставя на место только один элемент за проход. Сортировка кучей (или пирамидальная), о которой речь пойдет далее, – это максимально продвинутый вариант рассматриваемой сортировки.

Код для последнего рассматриваемого медленного метода, сортировки вставками (insertion sort), наверное самый короткий среди всех кодов, реализующих сортировки, поэтому этот метод иногда используют сложные быстрые сортировки для случаев, когда число сортируемых элементов мало (несколько десятков). Он чем-то похож на сортировку пузырьком, так как и тут и там последовательно сравниваются соседние элементы. Но сортировка вставками ищет для очередного элемента правильную позицию в уже отсортированной части данных, а не просто выталкивает экстремальный элемент в крайнюю позицию. При таком подходе также не нужна дополнительная память. Как и пузырьковая сортировка, сортировка вставками очень быстра на упорядоченных данных и быстрее на частично упорядоченных. В последним случае заметно быстрее пузырьковой. Обычно сортировка вставками несколько быстрее сортировки выбором. И в отличие от последней, она, как и сортировка пузырьком, – устойчива. Хуже всего сортировка вставками работает с данными с обратным порядком, с которыми она иногда становится самой медленной из медленных. Для тестов была использована следующая реализация. Её можно немного ускорить, если использовать не линейный, а бинарный поиск, например, функцией std::bsearch. Значительного ускорения можно будет добиться, если использовать структуру типа списка, вставка элемента в которую проходит очень быстро. Можно ещё заметить, что это наиболее естественная сортировка – её, например, обычно интуитивно используют, играя в карты.

Сортировка Шелла (shell sort) является самой простой среди быстрых методов и вполне пригодной для реализации только начинающими изучать программирование учащимися. Она является лишь некоторым видоизменением пузырьковой сортировки. Разница между ними только в том, что в сортировке Шелла расстояние между сравниваемыми элементами берётся меняющимся от прохода к проходу, от большего на первом проходе, до 1 на последних, таким образом, на этих последних проходах метод Шелла вырождается в примитивную сортировку пузырьком. Дональд Шелл опубликован базовый алгоритм сортировки, получившей его имя, в 1959 году. Таким образом, это одна из первых универсальных сортировок, которые работают быстро. Для сравнения, алгоритм быстрой сортировки был опубликован спустя два года, а популярные ныне сортировка Тима или интроспективная сортировка стали известны только в 90-е. C cортировкой Шелла связаны несколько интересных нерешённых математических проблем, главная из которых – это как оптимально выбирать смещения между сравниваемыми элементами. Удалось найти некоторые рекордные последовательности, например, A102549. Такие последовательности находят путем колоссальных вычислений, поэтому они имеют очень небольшую длину, A102549 – это всего 8 элементов, что хватает только для данных до примерно из 3000 элементов. Для больших данных продолжения нужно искать почти наугад. Использовал значения, близкие степеням числа 2, e, 2.25 и 3. Простые числа, близкие степеням 2 показали наихудшие результаты, заметно уступая лучшим. А вот остальные три варианта оказались примерно одинаковыми с точки зрения влияния на быстродействие и наверное весьма близкими к оптимальным. Причем в этих трёх случаях использование простых чисел не давало осязаемых преимуществ. Любопытно, что смещения предлагаемые в Википедии (с основанием 2.25) на основании ссылок на соответствующие труды, не показали на тестах лучших результатов, хотя и их отличия от лучших были весьма незначительны (не более 5-10%). Использование A102549 в качестве начальной также не дало никаких заметных результатов. Михаил Опанасенко также пытался разгадать сортировку Шелла и получил интересный результат о том, что смещения, выбираемые по формуле s_n+1=10s_n/3, дают очень хороший эффект и возможно даже, что близкий к идеальному. Мои результаты это подтверждают. В многих случаях именно такие смещения дали наилучший результат, хотя это было и не всегда и отрыв от ближайшего результата был совсем невелик (примерно 5%). Мой код для реализации сортировок Шелла использует маленькие таблицы со смещениями, хотя если не использовать простые числа, то эти смещения для таблиц можно почти мгновенно вычислить, как это и сделано в реализации одного из приведенных вариантов этой сортировки.

Интересно, что если брать смещения близкие степеням тройки несколько иначе и использовать несколько другой алгоритм (см. реализацию), то на 32-битных числах будем получать скорости, близкие к лучшим, но на более длинных числах и на строках будем получать существенное замедление, иногда более, чем на 100%. Результаты по лучшему алгоритму, использованному oms7, также есть в следующей далее таблице, но он, хотя и показывает хорошие по порядку результаты, по абсолютным значениям заметно отстаёт от лидеров.

Будет ли когда-нибудь найден способ находить оптимальные смещения? Возможно, но осмелюсь предположить, что ещё не скоро. Сортировка Шелла используется в ядре Linux, а в, как минимум, в одной библиотеке С её код используется для стандартной функции qsort(). Теоретически доказано, что скорость работы оптимальной сортировки Шелла по порядку лишь незначительно медленнее «настоящих» быстрых логарифмических методов. Действительно, зависимость среднего времени обработки данных от их размера для оптимальной сортировки Шелла описывается формулой ∽N(log N/log log N)², которая даже для весьма больших N весьма близка к типичной для других быстрых методов формуле ∽Nlog N. Обычно сортировка Шелла часто даже быстрее теоретически более быстрых по порядку методов и начинает чуть уступать им лишь, при обработке довольно больших массивов (порядка 10-в миллионов элементов). Этой сортировке совершенно не нужна дополнительная память и она стабильно ведёт себя для самых разных вариантов заполнения данных, выгодно отличаясь этим от быстрых сортировок. Свойством устойчивости метод Шелла не обладает.

Быстрая сортировка (quick sort) лишь незначительно сложнее алгоритма Шелла и до сих пор является одним из самым быстрым способом упорядочить случайно разбросанные данные. Однако у этой сортировки есть несколько недостатков. Ей требуется дополнительная память и для очень редких случаев она работает крайне медленно, по квадратичной зависимости. Главная идея этого метода в разделении данных на две части: данные в одной части должны быть больше или меньше (зависит от выбранного порядка), чем в другой. Существует несколько способов такого разделения. В идеале при каждом делении обе части должны получаться примерно одинаковыми по размеру, а хуже всего получается тогда, когда при делении одна из частей получается состоящей только из одного элемента. Рассмотрим несколько реализаций алгоритмов быстрой сортировки, в частности, метод Хоара, в котором опорный, делящий данные на две части элемент выбирается из середины сортируемых данных.

Рассмотрим также чрезвычайно компактный алгоритм Ломуто, который иногда чуть (примерно на 1%) быстрее рассмотренного метода Хоара. Однако, на типовых частных случаях, например, на упорядоченных, обратных или маловариантных данных метод Ломуто показывает чрезвычайную медленность. Кроме того, среди рассмотренных вариантов быстрой сортировка эта оказалась при практических прогонах самой жадной к размеру стека: при сортировке относительно небольших массивов только этой сортировке не хватило 8 мегабайт для стека, пришлось ставить через ulimit этот размер побольше. Такая жадность к стеку приводит при обработке больших данных (десятки миллионов строк) и к существенному замедлению работы, природу которого назвать затруднюсь. Могу лишь констатировать, что с такими данными эту и сортировку из следующего абзаца лучше не использовать.

Метод Ломуто в качестве опорного выбирает последний элемент, но возможно реализовать быструю сортировку вообще без опорного элемента, точнее выбор такого элемента здесь происходит как результат уже произведенной бисекции данных. Такая сортировка по скоростным характеристикам оказалась близкой к методу Ломуто, хотя обычно чуть быстрее, а в экстремальных случаях – заметно быстрее Ломуто, но медленнее Хоара.

В 2009 был опубликован алгоритм быстрой сортировки с двумя опорными точками, который стал стандартным для языка Java. Этот алгоритм на 20% уменьшает число перестановок по сравнению с лучшими типовыми, но число сравнений не меняется. Его автор – Владимир Ярославский. Действительно работает, как правило, быстрее других быстрых сортировок. Я немного его оптимизировал, использовав давно известный факт, что на архитектуре x86, swap работает обычно быстрее, чем присваивание, а для строк С++ – намного-намного быстрее. Все рассмотренные до сих пор быстрые сортировки не обладают свойством устойчивости.

Дополнительная память для быстрых сортировок нужна для организации рекурсивных вызовов. Однако, второй такой вызов можно заменить на цикл, проведя оптимизацию хвостовой рекурсии, которая по скорости может не дать никаких выигрышей, но существенно снижает размер используемых дополнительных данных. Я реализовал вариант сортировки Хоара с такой оптимизацией. Кроме того, в системных программах можно проверять указатель стека и если он приблизился к критическому значению, то можно просто сбросить все рекурсивные вызовы и начать сортировку заново – для этого случая очевидно, что нужно использовать вариант быстрой сортировки, не замедляющейся на почти упорядоченных данных, например, предложенный выше вариант Хоара. Борьба с использованием дополнительной памяти может считаться главной идеей быстрой сортировки из стандартной библиотеки языка С в GCC. В ней вообще отказались от рекурсии. Вместо неё используют её симуляцию, что позволяет на треть сократить нагрузку на стек. Код получился немаленький, около 150 строк. Об этой сортировке ещё будет небольшой материал ниже.

Сортировка хешем (hash sort) может быть очень быстрой, близкой к ∽N. Однако, иногда она может работать и по квадратичной зависимости. Скорость работы этого метода сортировки очень зависит от входных данных. Если данные равномерно распределяются хеш-функцией по вспомогательному массиву, то получаем максимально быструю линейную зависимость. А если все данные сгруппированы возле нескольких далеко отстоящих друг «центров масс» или когда много одинаковых элементов данных, т. е. когда случается много хеш-коллизий, то получаем худшую зависимость типа ∽N². Как и для сортировки деревом, для сортировки хешем нужно довольно много дополнительных данных, в приводимом листинге кода нужно, например, 12 дополнительных байт на каждое сортируемое целое число (int32, x86-64). Интересным свойством сортировки хешем является отсутствие операций сравнения между элементами данных, что отличает эту сортировку от всех рассмотренных выше. Точнее эти операции нужны только для случая коллизий. При сортировке данных, где ключ совпадает со всем элементом данных, можно использовать дополнительный счетчик числа одинаковых элементов, но это скорее сомнительная оптимизация. Можно ещё использовать бинарное дерево вместо списка для хранения данных хеш-коллизий, это значительно ускоряет работу для отдельных частных случаев, когда много коллизий, но в целом работа при использовании бинарного дерева во многих случаях замедляется и это при том, что в таком случае на элемент данных приходится хранить почти 100 байт дополнительной информации. Я реализовал три варианта хеш-сортировки с использованием бинарного дерева: один использует неупорядоченное дерево, а два других – стандартные деревья из библиотек std и boost. Хеш-сортировка практически непригодна для сортировки текстовых строк, за исключением совсем коротких, так как для таких данных невозможно сделать хорошую хеш-функцию. Стандартный хеш С++ (unordered_multiset) для сортировки у меня приспособить не получилось: пробовал использовать монотонные хеш-функции и упорядочивающие отношения вместо равенства – это не сработало.

Сортировка массивом (array sort) очень похожа на предыдущую. Также используется вспомогательный массив, куда хеш-функцией заносятся значения. При коллизии нужно сдвинуть непрерывный фрагмент занятых элементов на позицию влево или вправо, освобождая указываемую хеш-функцией позицию для нового элемента. Для получения хорошей скорости нужно, чтобы вспомогательный массив был в несколько раз (от 2-3) больше исходного. С ростом размера вспомогательного массива скорость работы увеличивается только до некоторого предела, зависящего от сортируемых данных и связанной с ними хеш-функции, а затем (типично с 4-5) падает. Скорость работы – примерно такая же как и у хеша, но на хороших данных чуть быстрее, а на плохих – заметно медленнее. Этой сортировке также надо довольно много дополнительной памяти. Если ограничить количество элементов в сортируемом массиве числом, чуть большим четырех миллиардов, то утроенный вспомогательный массив потребует столько же дополнительных данных, что и сортировка хешем, а усемеренный – 28 байт, что заметно меньше, чем для сортировки деревом, или намного меньше, чем хешем с деревьями. Эта сортировка также почти непригодна для работы со строками. В Википедии статьи про такой алгоритм нет, а вот моя реализация.

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

Одна из самых быстрых сортировок, которая вообще никогда не используют сравнений, – это известная ещё с XIX века поразрядная сортировка (radix sort). Её идея очень проста – нужно работать с группами разрядов представления данных (для тестов брал группы из 8, 11 и 16 разрядов). По каждой группе строятся таблицы, а результаты потом сравнительно простым способом объединяют. Существует два основных способа использовать поразрядную сортировку. Для сортировки чисел разряды удобнее брать справа налево (это вариант LSD – Least Significant Digit), а для сортировки строк слева направо (это вариант MSD – Most Significant Digit). Поразрядная сортировка часто бывает значительно быстрее любых других методов упорядочения данных. Удивительно, что поддержка поразрядной сортировки до сих пор не слишком значительна: её нет ни в boost, ни в стандартной библиотеке С++, мне неизвестен даже её вариант для какой-нибудь известной библиотеки для работы с числами или строками С++. У этой сортировки есть, конечно, и недостатки. Она очень чувствительна к типу данных для сортировки, например, нужно иметь свой вариант такой сортировки для данных каждого размера, нужно делать специальный варианты для беззнаковых и знаковых целых чисел, а поддержка работы с вещественными числами может потребовать совсем немаленьких усилий. Её вариант при использовании порядка от младшего байта к старшему обычно требует дополнительной памяти, чуть большей, чем для исходных данных (это существенно меньше, чем для сортировки хешем или массивом и тем более деревом). Кроме того, этот вариант малопригоден для сортировки длинных строк. Мой код для этой сортировки здесь, он основан на коде из упоминавшейся статьи oms7. Вариант с обратным порядком обработки байт более универсален и очень хорошо подходит для сортировки строк. Этот вариант можно реализовать без использования дополнительной памяти (цена этому – потеря свойства устойчивости), как это сделано в функции radixsort() библиотеки bsd. Мой код для этого варианта также основан на коде oms7, он ценой использования дополнительной памяти, несколько большей размера исходных данных, имеет свойство устойчивости, но неоптимизирован для строк и поэтому показывает значительно худшие характеристики производительности, чем аналогичная по назначению функция sradixsort() из уже упомянутой библиотеки bsd. Эта сортировка может показать удивительно плохие результаты при работе с маленькими числовыми массивами, работая на несколько порядков медленнее, чем даже пузырьковая, хотя речь идет об очень маленьких величинах не более нескольких миллисекунд и эту разницу непросто заметить. Так получается из-за того, что она использует вспомогательные массивы небольшого размера, но при сортировке данных маленького размера эти небольшие размеры могут оказаться больше самих сортируемых данных. Для избежания замедления вариант «слева направо» использует сортировку вставками вместо основной в таких случаях. В заключении, стоит отметить, что это единственная известная мне относительно популярная сортировка, всегда достоверно работающая со скоростью ∽N, но коэффициент пропорциональности здесь зависит от размеров элементов данных и для строк или длинных чисел он может быть весьма ощутим.

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

Далее рассмотрим некоторые сортировки, которые можно встретить в стандартных библиотеках.

Начнём с быстрой из стандартной библиотеки C (qsort, вариант GCC), о ней уже писал. Могу здесь только добавить, что это сортировка как и другие С-сортировки (например, следующие далее из библиотеки BSD) непригодны для работы с объектными данными, в частности, строками С++, что вызвано тем, что такие данные не являются POD. Имея исходники, проблему легко решить, заменяя операции типа memcpy на обычные присваивания. Можно ещё заметить, что в некоторых стандартных библиотеках С, эта сортировка может быть не обязательно именно быстрой, её могут заменять на другие. В текущей версии для GCC эта сортировка даже обладает свойством устойчивости. С упомянутыми си-сортировками при сборе данных иногда возникали сюрпризы, они могли, например, работая с типом std::vector через функциональный объект, создавать сложности – могу порекомендовать использовать её с объектными данными с осторожностью. По данным прогонов эта сортировка иногда относительно медленная: она заметно уступает по скорости другим реализациям быстрой сортировки при работе с числами, но при работе с си-строками она лучшая, лишь сортировке с двумя опорными точками иногда получается её обогнать, но на длинных строках стандартая qsort обгоняет её почти всегда. Самое интересное открылось при попытке отсортировать с её помощью миллиард целых чисел – оказалось, что заполнение типа 7 приводит к временной зависимости, близкой к квадратичному закону, т. е. к возможному «процессингу» длительностью до нескольких лет (не стал ждать окончания и остановил это на 21 часу прогона). На меньших данных эта сортировка умеет обычно подбирать опорные точки, с которыми работает быстро.

Интроспективная сортировка используется в стандартной библиотеке C++, хотя какой в точности метод, используется в std::sort зависит от реализации, привёл сведения только по GCC. По данным прогонов, это вторая по скорости после spread-сортировки при работе с числами, причем преимущество spread-сортировки небольшое (от почти 0 до 30%), а вот с сортировкой строк всё значительно хуже – она может уступать лидерам в 3-4 раза. Это фактически быстрая сортировка, в которой учитываются два частных случая: 1) если число рекурсий стало слишком большим, то происходит переключение на сортировку кучей; 2) если число элементов для сортировки мало, то происходит переключение на сортировку вставками.

Устойчивая сортировка из стандартной библиотеки С++ (std::stable_sort), как следует из названия, имеет свойство устойчивости – она сохраняет относительный порядок между элементами с одинаковым ключом. Это свойство сравнительно редко является необходимым, хотя пишу об этом скорее голословно, только на основании собственного опыта. Может использовать дополнительную память, что делает её быстрее. Удивительно, но эта сортировка нередко оказывается быстрее std::sort.

В сверхпопулярном языке питон в качестве стандартной используется сортировка Тима. Для тестов использовал её вариант из github-репозитория. Она показывает рекордно хорошие результаты на частично-упорядоченных данных, но в среднем всё же заметно медленнее лидеров. Обычно её скорость – это среднее между быстрыми сортировками и сортировками Шелла, хотя на строках она иногда бывает близка к лидерам. Обладает свойством устойчивости. Она реализует относительно непростой алгоритм, в стандартной реализации которого в 2015 была обнаружена ошибка, которая, впрочем, требует скорее нереальной ситуации для своего проявления.

В С-библиотеке BSD есть поразрядная сортировка (radixsort) и её устойчивый вариант (sradixsort). К сожалению, обе эти сортировки можно использовать только для С-строк. Как будет видно из данных по тестам – это сегодня наибыстрейший способ отсортировать строки и поэтому удивительно, что нет её стандартного варианта для строк С++.

В С-библиотеке BSD есть ещё сортировка слиянием (mergesort). Эта сортировка известна как одна из самых быстрых для данных с последовательным доступом (файлы, списки) и возможно используется в стандартной библиотеке С++ для сортировки списков (std::list и std::forward_list). Кстати, она известна ещё с 1948 и одним из её разработчиков был весьма небезызвестный математик и специалист по первым компьютерным системам фон Нейман. Из быстрых методов эта сортировка не выделяется лучшими характеристиками, хотя, как правило, она несколько быстрее методов Шелла. Она требует дополнительной памяти и обычно реализуется устойчивой.

Кроме того там ещё есть сортировка кучей (heapsort). Куча обычно используется для оптимальной организации очереди с приоритетами, но может использоваться и для сортировки. Сортировки кучей не требуют дополнительной памяти, но свойством устойчивости не обладают. По скорости для чисел она значительно (до 3-6 раз) медленнее, чем методы Шелла, но для не очень коротких строк строк она показывает совсем неплохие результаты, обгоняя (с ростом длины строки преимущество растет) методы Шелла.

Сортировка кучей есть и в стандартной библиотеке C++. Такая сортировка делается за две операции: построение кучи (std::make_heap) и затем собственно сортировка (std::sort_heap). Здесь в отличие от библиотеки bsd сортировка – это именно одна из операций для кучи. Обычно этот вариант сортировки несколько быстрее предыдущего (вариант bsd показывает лучшие результаты только на коротких числах и длинных си-строках).

Используя стандартную библиотеку С++, можно сортировать и бинарным сбалансированным деревом (std::multiset) – просто заполняем дерево, а затем обходим. Можно считать этот метод нерекурсивной быстрой сортировкой. Некоторая проблема возникает в том, что стандартый распределитель памяти отличается заметной неспешностью, поэтому для лучших результатов надо использовать свой распределитель, что ускоряет примерно на 10-30%. Можно ещё отметить, что такой метод требует очень много дополнительной памяти, с g++ на каждый элемент данных, помимо него самого нужно ещё хранить 32 байтa (на архитектуре x86-64) – интересно было бы попробовать хранить такое дерево как кучу, т.  без дополнительных байт. Если использовать boost::container::multiset, памяти нужно поменьше: только дополнительных 24 байта на элемент данных. Однако как boost, так и стандартная библиотека продемонстрировали один неприятный сюрприз – в процессе работы они иногда требовали больше памяти, чем было необходимо. Возможно это из-за балансировки бинарных деревьев. Коды – здесь.

В библиотеке boost есть spreadsort, алгоритм которой был изобретён уже в 21 веке. Это наиболее быстрый в целом на сегодня метод из присутствующих в известных библиотеках. Эта сортировка использует некоторые идеи поразрядной и подобно ей может быть довольно капризной к типу аргументов. Обычно это сортировка показывает рекордные результаты, иногда существенно лучшие тех, что у ближайших конкурентов. Единственное исключение – это сортировка С-строк, где она существенно уступает поразрядным методам из библиотеки bsd. При сортировке длинных С-строк она может уступать и другим методам, например, spin-сортировке или быстрой сортировке с двумя опорными точками. У spread-сортировки (boost v1.62) обнаружилась очень неприятная проблема — при сортировке небольших (до 1000 элементов) массивов С-строк она работает с ошибками.

Там есть ещё новый алгоритм pdqsort, улучшающий, как заявлено автором, интроспективную сортировку. Этот новый алгоритм, который пока ещё не описан в Википедии. Его результаты – хотя и неплохие, но не особо впечатляющие. Он медленнее std::sort на коротких целых, но быстрее на строках и длинных целых. В обоих случаях разница скорее незначительная. Лучшие результаты у этой сортировки получились для длинных С++-строк – здесь она уступает, хотя и заметно, только лидеру, spread-сортировке.

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

Закончим на flat_stable_sort из всё той же библиотеки boost. Это ещё один новый устойчивый алгоритм, который пока не описан в Википедии. Это безусловно быстрый метод, но несколько уступающий большинству других быстрых библиотечных методов. Он использует очень мало дополнительной памяти (ему, однако, всегда нужна таблица фиксированного размера 8 КБ) и часто заметно быстрее метода Шелла.

Рассмотрим таблицу времени (в мс) работы этих алгоритмов на компьютере с 8 ГБ оперативной памяти с процессором AMD Phenom™ II X4 955 @3.214 МГц. Компьютер работал в общей сложности несколько месяцев, а суммарный размер собранных данных в двух json-файлах, которые загружаются с таблицами, составляет почти 400 КБ. Тайминги приводятся по среднему от числа прогонов, для меньшего размера данных прогонов было больше. Работа с кэшем довольно сложным образом меняет скорость вычислений, поэтому полученные результаты в лучшем случае только приблизительны (могу предполагать, что неточности таймингов могут доходить до 20%). Полагаю, что на лучших современных процессорах для ПК результат может быть получен в 2-3 раза быстрее, но при этом нужно иметь в виду, что многие более современные процессоры работают, переключаясь между разными частотами и результат, полученный с ними, будет ещё более приблизительным.

Эта и следующая таблица – интерактивны. Помимо абсолютных значений таймингов можно посмотреть также их значения относительно среднего, медианы, минимума и максимума. Можно менять точность в знаках. Можно также получить отношения таймингов по разным видам заполнений и типам данных. Последнее, например, может показать, что сортировка С-строк заметно быстрее строк С++. Из методов сортировки также можно выбирать и собирать разнообразные подмножества. Можно, конечно, и устанавливать сортировку по любому столбцу. К сожалению, я не знаю как в статье на хабре использовать Javascript, поэтому таблицы доступны только по ссылкам. Для случая, если github.io окажется перегруженным, даю ещё резервные ссылки на первую и вторую таблицы.

Время измеряется в миллисекундах, но в законе временной зависимости, чтобы избежать слишком маленьких коэффициентов приводятся формулы для микросекунд. Таким образом, если подставляем в формулу значение для N, то результат надо ещё разделить на 1000, чтобы получить число, близкое к соответствующему из таблицы. Закон временной зависимости выводится на основании полученных таймингов, из сопоставления двух результатов (обычно берутся крайние). Проверить качество выведенного закона можно, используя опцию относительного отклонения (deviation) фактической величины от выводимой.

Некоторые общие выводы по результатам этой таблицы:

• лучшие shell-сортировки на данных размером до 10 миллионов элементов могут обгонять timsort и даже некоторые быстрые сортировки;
• timsort очень близка по скорости qsort (clib), иногда несколько обгоняя, а иногда наоборот отставая;
• heapsort и особенно treesort часто заметно тормозят, но на фоне пузырька или даже выбора видно, что это всё-таки быстрые методы. Интересно, что оба этих метода нередко имеют весьма близкие характеристики – они оба строят деревья. Легко заметить, что у heapsort и treesort зависимости хотя и явно не квадратичные, но очевидно и не Nlog N, а существенно хуже – сравните с сортировкой Шелла, которая с ростом объёма данных ведёт себя гораздо лучше, чем heapsort или treesort, при том, что она сама медленнее, чем Nlog N. Таким образом, практические реализации сортировок кучей и деревом не соответствуют их теоретическим спецификациям;
• данные по сортировкам строк показывают, что законы временных зависимостей здесь не такие как для чисел – на эти законы здесь как-то накладываются длины строк, которые сортируются. Мне, к моему сожалению, неизвестны формулы для известных сортировок, которые бы давали точные законы временных зависимостей при работе со строками;
• интересно, что скорость работы с вещественными числами примерно такая же как и целыми – это следствие того, что в современной архитектуре x86 сделаны очень эффективные оптимизации для работы со стеком;
• hash_sort показала совершено посредственные результаты, это возможно из-за того, что из-за использования дополнительной памяти резко падает эффективность работы кэшей процессора. На небольших случайных данных (менее ста тысяч элементов) сортировка хешем обгоняет лучшие быстрые (quick) сортировки. Можно ещё заметить, что возможно опять из-за кешей, некоторые результаты у этой сортировки очень странные, например, 10⁵, 10⁶ и 10⁷ 32-разрядных целых при использовании частично упорядоченного (partially ordered) заполнения сортируются за примерно одно и то же время! Какие-то почти квантовые эффекты. :) Уверен, что если поискать, то можно найти и другие труднообъяснимые результаты.

Добавлю ещё некоторые выводы по некоторым частным случаям:

• некоторые типы заполнения данных обнаруживают слабые места быстрых сортировок. Однако выбор опорного элемента сложным образом делает вероятность попадания на плохую для сортировки последовательность практически нулевой. Можно также выбирать опорный элемент на каждом проходе по разному или случайно. Возможно так и делают в qsort (clib). Рассматриваемый метод Хоара работает очень медленно только на специально сконструированных последовательностях, встретить которые случайно при практической работе – это случай с вероятностью менее 2^N-3/N!, то есть почти абсолютно невозможное событие. Хотя если рассматривать последовательности, на которых метод Хоара работает не максимально медленно, а только с существенным замедлением, то таких случаев гораздо больше, что, однако, оставляет вероятность случая недопустимо медленной обработки данных по-прежнему практически ничтожной, хотя и весьма раздражающей своим отличием от нуля. Также почти невозможно случайно получить данные, на которых быстрая сортировка с двумя опорными точками, будет работать медленно, по квадратичному закону. Варианты быстрых сортировок Ломуто и без опорного элемента показывают очень плохие результаты почти на всех частных случаях заполнений;
• на некоторых частных случаях, самая медленная «пузырьковая» сортировка даёт отличные результаты, а одни из самых быстрых, quick-сортировки, наоборот очень плохие;
• сортировка хешем показала очень плохой результат на заполнениях типа 8 и 9, это объясняется тем, что монотонная последовательность берётся из последовательных величин, начиная с меньшего, а 1% случайных чисел берётся из диапазона от меньшего до максимального значения, что скучивает все последовательные 99% данных в один элемент хеша. Этот случай очень хорошо демонстрирует проблемы, которые могут возникнуть при использовании этой сортировки или сортировки массивом с неизвестными данными;
• сортировка выбором ведёт себя очень стабильно на всех типах заполнения, heap- и tree-сортировки также довольно стабильны, без явных пиков и провалов. Это верно, конечно, и для сортировок Шелла, а также большинства других быстрых методов из стандартных библиотек.

Теперь пора рассказать об типах данных, использованных с сортировочными алгоритмами:

1. целые числа, 32-битные знаковые (int32_t), но использовались только неотрицательные. Другие числовые данные также брались только неотрицательные – это не снижает общности полученных результатов, но делает их получение для некоторых алгоритмов существенно проще;
2. целые числа, 64-битные знаковые (int64_t);
3. целые числа, 128-битные знаковые (__int128 – поддерживаются, как минимум, GCC);
4. структуры из пяти целых чисел (int32_t), одно из которых используется как ключ (INT1P4). При сортировке таких данных более существенно на время вычислений начинает влиять количество перестановок, поэтому методы с меньшим числом перестановок получают некоторое преимущество;
5. вещественные числа типа двойной точности, double (float numbers);
6. короткие строки C++ и С. Брались строки длиной от 1 до 16 (strings short и c-strings short);
7. строки С и С++ средней длины, длина которых от 1 до 256 (strings и c-strings);
8. длинные строки С и С++, длина которых от 1 до 2²⁰ (это чуть больше миллиона), причем строки подбираются так, что их средняя длина не превосходит 512, – так подбирались строки только для случайного заполнения, для остальных случаев просто брались строки длиной от 1 до 512 (strings long и c-strings long).

А также о способах заполнения исходного массива для сортировки:

1. случайно;
2. строго по возрастанию (упорядоченные, ordered);
3. строго по убыванию (обратного порядка, reversed);
4. случайные величины из диапазона от 0 до 99 (малого разброса, low variation 100);
5. случайная последовательность из 0 и 1 (малого разброса, low variation 2);
6. константой 0 (малого разброса, low variation 1);
7. последовательность, приводящая приведённый вариант qsort (Hoare) к самому медленному исполнению. Любопытно, что таких последовательностей ровно 2^N-3 среди всех последовательностей длины N из различных элементов;
8. строго по возрастанию, с вставкой 1% случайных чисел (partially ordered);
9. строго по убыванию, с вставкой 1% случайных величин (partially reversed).

Следует подчеркнуть, что случайные данные (random) – это самый типичный случай заполнения массива, все остальные способы – это крайне редкие и даже почти невозможные при нормальной работе частности.

Рассмотрим ещё результаты тестов, где сортировки работают со всеми возможными последовательностями данных. Число таких последовательностей равно факториалу от их длины, таким образом, для последовательностей длины 12 существует 479'001'600 вариантов – такое их количество хороший современный ПК обсчитает за менее, чем минуту. Если мы возьмём последовательности длины 14, то получим уже 87'178'291'200 вариантов на несколько часов работы компьютера. Поэтому в следующей таблице – среднее время (в тактах процессора, получаемых через инструкцию RDTSC) одной сортировки при сортировке всех перестановок длиной только до 12. В качестве данных берутся прежние числовые типы и короткие строки. Конечно, можно было заметить, что последовательности с повторяющимися элементами не рассматриваются. Однако, осмелюсь предположить, что их наличие качественно не изменило бы результатов, но могло существенно замедлить их получение.

Результаты по таким маленьким данным не слишком репрезентативны и особенно по сложным методам сортировки, но представление о поведении сортировок они всё-таки дополняют. Некоторые сортировки, насколько мне известно, заменяют свой основной алгоритм на другой при работе с маленькими массивами – это сортировки spread, быстрая с двумя опорными точками и radix_msd (две последних используют вставки). А некоторые сортировки (flat_stable и radix) используют маленькие таблицы, но при крошечных размерах данных эти таблицы оказываются гораздо большими самих данных, что сильно тормозит эти методы на фоне других и производит странные результаты. Странные результаты также получаются и у других поразрядных сортировок и у сортировок хешем и массивом. Такие необычные результаты легко объясняются тем, что время подготовки данных перед сортировкой у этих методов для маленьких данных больше времени самой сортировки. Конечно, при измерении таких маленьких временных интервалов (наносекунды) влияние разнообразных погрешностей на выводимый закон гораздо выше, чем в предыдущей таблице. Поэтому законы получились очень приблизительные, часто «с заносом» к преувеличенным значениям. Последнее частично объясняется тем, что при работе с маленькими данными время собственно сортировки становится сравнимым с временем вызова функции сортировки и нескольких необходимых вспомогательных операций по замеру времени. Программа старается вычесть названные накладные расходы из выводимого результата, но это получается делать скорее очень приблизительно. При всём этом осмелюсь ещё предположить, что, сравнивая результаты для разных типов данных и принимая в расчет сделанные замечания, можно делать иногда предположения, не очень далёкие от точных.

В заключении ещё одна таблица, которая показывает насколько много требуется разным тестируемым методам сортировки дополнительной памяти. Очевидно, эта величина зависит от системы. В моих тестах, как уже писал, это x86-64, GCC. Буква Т в ней означает размер типа в байтах (в этот размер длина строки не входит: для си-строк – это размер указателя, для строк си++ – это размер дескриптора, 32 байта для x86-64 GCC), буква L – средняя длина типа в байтах (для чисел это равно Т, а для строк это средняя длина строки), буква А может иметь значение 1 или 0 – это выравнивание до 64-битной границы, а буква M – это выравнивание от стандартного распределителя памяти (оно предположительно выравнивает на 32-байтную границу). Значок ^* означает, что данные по этому типу сортировки были получены только на основании анализа чтения поля VmRSS из /proc/PID/status (упомянутое поле – это размер программы-процесса).

Таблица дополнительной памяти

Метод	Зависимость
array*1	(T + 1/8)N
array*k, k>1	(T + 4k)N
bubble	0
clib_qsort	от ≈TN/2 до ≈TN*
flat_stable	≈TN/256
hash	(T + 8 + 4A)N
hashbt	(T + 12)N
hashbt_boost	(56 + T + 4A + M)N
hashbt_std	(80 + T + 4A + M)N
heapsort	0
insertion	0
mergesort_bsd	от ≈Tlog2N до TN*
pdq	TlogN
quicksort	от ≈16log2N до 16N
quicksort_tco	от 0 до N
radix	≈TN
radix8_trie	от ≈TN + 24L до ≈(T + 24L + 12)N
radix_bsd	0
radix_msd	≈TN
selection	0
shell	0
spin	TN/2
spread	≈0
sradix_bsd	≈TN*
stlsort	от 0 до до ≈Tlog2N*
stlstable	от 0 до ≈TN/2*
timsort	от 0 до ≈TN*
tree_boost	(T + 24)N
tree_stl	(T + 32)N

Существуют, конечно, и другие методы сортировки как примитивные, так и быстрые. В библиотеке boost есть параллельные алгоритмы, позволяющие получать преимущества от наличия дополнительных процессорных ядер в системе. Можно ещё вместо std::multiset использовать самоупорядочивающийся контейнер boost::container::flat_multiset, но это работает очень медленно.

Пользуюсь случаем, чтобы сказать несколько замечаний о библиотеке boost вообще. Рекомендую не проходить мимо. Даже те возможности, которые есть в стандартной библиотеке, в boost, как правило, реализованы лучше, а иногда (как, например, регулярные выражения) значительно лучше. Если говорить о контейнерах, то в boost их заметно больше, а те, что совпадают со стандартными, иногда несколько быстрее и имеют часто небольшие, но приятные улучшения. Boost более тщательно проверяет соответствие типов, что иногда может помочь с обнаружением почти неуловимых ошибок, которые обычно себя не проявляют, но в некоторых обстоятельствах способны неожиданно активироваться. К недостаткам boost относиться безусловно совершенно нечитаемые и огромные по объёму сообщения об ошибках компиляции на многих конструкциях из этой библиотеки – это, хотя и в меньшей степени, относится и к стандартной библиотеке. Разработчикам С++ пора с этим уже что-то делать.

Все файлы с тестами и некоторые другие смежные материалы можно взять из моего репозитория. Если кому-то интересны сырые исходные данные, то их можно взять тут (1.4 МБ). Буду рад любым комментариям, критике и добавлениям.