Алгоритм<spreadsort>, используемый в этой библиотеке, предназначен для обеспечения наилучшей возможной производительности в наихудшем случае. Он обеспечивает лучшее из& # 119926; (N*log (K/S + S))и& #119926; (N*log(N))наихудшее время, гдеKявляется журналом диапазона. Журнал диапазона обычно представляет собой длину в битах типа данных; 32 для 32-битного целого числа.

<flash_sort>(другой гибридный алгоритм), для сравнения:& #119926; [N]для равномерно распределенных списков. Проблема в том, что<flash_sort>является просто MSDрадикс-сортомв сочетании си #119926; [N*N]вставкой для решения небольших подмножеств, где MSD Radix Sort неэффективен, поэтому он неэффективен с фрагментами данных вокруг размера, при котором он переключается на<insertion_sort>, и в конечном итоге работает как улучшенный MSD Radix Sort. Для неравномерного распределения это делает его особенно неэффективным.

<integer_sort>и<float_sort>вместо этого используйтевставку, которая обеспечивает& #119926; (N*log(N))для этих средних фигур. Кроме того, производительность<flash_sort>и #119926; [N]для равномерного распределения достигается за счет промахов кэша, которые на современных архитектурах чрезвычайно дороги, и при тестировании на современных системах в конечном итоге происходит медленнее, чем сокращение данных несколькими, удобными для кэша шагами. Также стоит отметить, что на большинстве современных компьютеров<log2(available RAM)/log2(L1cache size)>составляет около 3, где промах кэша занимает более чем в 3 раза больше времени, чем случайный доступ в кэше, а размерmax_splitsнастроен на размер кэша. На компьютере, где промахи кэша не так дороги,max_splitsмогут быть увеличены до большого значения или полностью устранены, и<integer_sort/float_sort>будет иметь такую же& #119926; [N]производительность на четных дистрибутивах.

Адаптивный левый радикс (ALR) похож на<flash_sort>, но более удобен для кэша. При этом используется вставка_sort. Поскольку ALR используети #119926; (N*N)<insertion_sort>, нецелесообразно использовать сортировку резервных копий на основе сравнения в больших списках, и если данные группируются небольшими фрагментами чуть выше размера резервных копий с несколькими выбросами, сортировка на основе радикса многократно повторяется, делая небольшую сортировку с высокими накладными расходами. Асимптотически ALR по-прежнему& #119926; [N*log(K/S + S)], но с очень маленькимS(примерно 2 в худшем случае), который неблагоприятным образом сравнивается с 11 значением по умолчаниюmax_splitsдля Spreadsort.

ALR также не имеет запасаи #119926; [N*log(N)], поэтому для небольших списков, которые не распределены равномерно, он крайне неэффективен. См. примеры<alrbreaker>и<binaryalrbreaker>; либо заменить вызов на сортировку вызовом ALR и обновить ALR_THRESHOLD вверху, либо в качестве быстрого сравнения сделать<get_max_countreturn ALR_THRESHOLD>(20 по умолчанию на основе бумаги). Эти небольшие тесты занимают в 4-10 раз больше времени с ALR, чемstd::sortв авторском тестировании, в зависимости от тест-системы, потому что они пытаются сортировать очень неравномерное распределение. Нормальный спрэдсорт делает с ними гораздо лучше, потому что<get_max_count>предназначен для минимизации времени выполнения в худшем случае.

<burst_sort>— эффективный гибридный алгоритм для строк, использующий значительную дополнительную память.

<string_sort>использует минимальную дополнительную память для сравнения. Сравнение скорости между ними не было сделано, но лучшая эффективность памяти делает<string_sort>более общей.

<postal_sort>и<string_sort>похожи. Прямое сравнение производительности было бы желательно, но эффективная версия<postal_sort>не была найдена в поиске источника.

<string_sort>больше всего похож на алгоритмамериканского флага. Основное отличие заключается в том, что он не утруждает себя попытками оптимизировать обработку пустых ведер, а просто проверяет, равны ли все символы в текущем индексе. Другие различия заключаются в использованииstd::sortв качестве алгоритма резервного копирования и большего размера резервного копирования (256 против 16), что делает обработку пустых свай менее важной.

Другим отличием является отсутствие ограничения размера стека. Из-за проверки равенства в<string_sort>, потребовалось бым*мпамяти струн, чтобы заставить<string_sort>создать стопку глубиным. Эта проблема не является реалистичной в современных системах с многомегабайтными ограничениями стека, где основная память будет исчерпана, удерживая длинные строки, необходимые для превышения предела стека.<string_sort>можно рассматривать как модернизациютипа американского флага, чтобы использоватьв качестве запасного алгоритма. В авторском тестированиисорт американского флага(на<std::strings>) имел сопоставимое время выполнения синтрозортом, но создание гибрида этих двух позволяет снизить накладные расходы и существенно повысить производительность.