Comments 39
Кратко.
Я написал новый пупер алгоритм сортировки, он работает быстрее, чем быстрая сортировка, но я не уверен, что она работает правильно.
Судя по коду, алгоритм действительно сортирует, но не учтен худший случай для алгоритма, а именно случай, в котором localCatchUp минимальных и localCatchUp максимальных элементов на каждой итерации рекурсии оказываются в начале сортируемого массива.
Такая ситуация соответствует выбору почти минимального элемента в алгоритме быстрой сортировки.
там вроде в коде есть проверка идентичности с результатом квиксорта (да, это не строгое доказательство)
А худший случай так и остался по сложности О(n^2)? Тогда чем эта сортировка лучше сортировки слиянием?
(а) какая сложность по памяти?
(б) что по сравнению с timsort?
(б) с тимсортом не сравнивал
O (3n)
А у квиксорта — O(log n), если мне память не изменяет.
с тимсортом не сравнивал
А зря, потому что про него известно, что он быстрее квиксорта.
(а) O (3n)
У вас на момент рекурсивного вызова выделено и не освобождено О(n) памяти (массивы restFirst и restSecond). Глубина рекурсии О(log n). Соответственно, сложность по памяти О(n * log n).
UPD: пардон, там arr освобождается. Все таки O(n)
с тимсортом не сравнивал
Сравнил за вас.
Тимсорт лучше чуть менее, чем везде.
Время выполнения на моей машине:
qsort std::sort timsort newSort
random 79.56 51.2199 85.0301 122.1
sorted 36.9301 13.1499 0.339997 4.02001
part-sorted 78.5999 46.2 28.0399 31
chunk-sorted 93.1501 43.41 2.73001 11.7
rsorted 37.88 10.57 0.789863 4.54
part-rsorted 71.7799 35.73 36.5 32.44
chunk-rsorted 94.85 47.71 3.04001 13.71Исходник (слегка модифицированный авторский): https://pastebin.com/kQVC6Cam
В 4 случаях из 7 всем алгоритмам подаются абсолютно одинаковые массивы. В остальных 3 случаях данные отличаются, но их характер — нет. Необъективным было бы сравнивать одного случайной значение с другим. И на основе одного сравнения делать выводы. Здесь же этих случайных значений сто миллионов штук. И они имеют одинаковое распределение. Так что сравнение вполне себе объективно.
Впрочем, если несогласны — добавьте строчку srand(1); между 982 и 983 строками. Получите одинаковые массивы и сравнение, которое на 95% объективнее. Вот только результат сравнения будет таким-же.
На самом деле очень странно наблюдать такое поведение.
Потому что измерять производительность в отладочной сборке — все равно что измерять скорость гоночных болидов в болоте. Включите оптимизации компилятора и картина резко изменится. Хотя с моей может на 100% и не совпасть. Я собирал с gcc.
А бывает наоборот. Я как-то несколько лет назад находил багу в .NET, когда неудачный алгоритм инлайна в релизном режиме приводил к экспоненциально долгому и также экспоненциально прожорливому потреблению памяти JIT. Сейчас (после моего репорта в core, но проявлялось и в framework) багу уже пофиксили. Хотя, на мой взгляд и неидеально пофиксили, но всяко лучше, чем было.
Запускал из-под 19 студии.
Ээээ, вы тесты гоняли на дебажной сборке?
(судя еще и по Debug на скриншоте)
Но это дало бы доп. прирост к скорости.
Не дало бы. Ваши сливаемые массивы формируются совершенно иным образом, чем в тимсорт. Там за счет галопа получается выгода от частичной упорядоченности входных данных. У вас же на момент слияния данные из входного массива разбросаны по 3 другим массивам довольно таки произвольным образом.
Впрочем, опять таки — никто вам не мешает реализовать таки галоп и собственноручно в этом убедиться. Ну или получить убийцу тимсорта и тем самым наглядно показать, что я не прав.
- Зачем ручное управление памятью? Вектора тормозят? Меряли?
- Зачем битовая арифметика? У вас простое возведение в степень тормозит? Аналогично с «i & 1».
- «удаляем массив размером 2 * len элементов » или «2 ^ len»?
- "/// works only if arr is pointer assigned by new keyword" — вообще грусть какая-то, ИМХО.
- Оценивали сложность по памяти?
2) Опять же мне приятней писать i & 1 чем i % 2 != 0
3) Мы выделяли 2 * len памяти, соответственно освобождаем тоже 2 * len
4) Это решается простой обёрткой над представленной реализацией. Мы же можем полностью скопировать массив и сортировать копию. Предоставленная здесь функция рекурсивная, и в ней есть хитрые манипуляции с памятью.
5) Без обёртки O (3n). Если написать над ней обёртку, то O (4n).
Без обёртки O (3n). Если написать над ней обёртку, то O (4n).
O(3n) = O(4n) = O(100500n) = O(n)
3). Зачем делать len << 1, а не просто len * 2, если в комментариях у вас умножение? Попахивает, простите, байто
5). Хитрые манипуляции имеют смысл? Константы в O-нотации принято игнорировать.
Тем более, с хитро скопируемой памятью.
Я не вникал полностью в предложенный алгоритм, но для квиксорта это однозначно ненормальное поведение.
Тут снова возникает вопрос о правильной организации бенчмарка.
Иначе получается, что getCPUTime() (кстати, что оно такое?) меряет непонятно что.
Вдруг винда свопнтуься решила/апдейт качает или в телеграм нотификации пришли?
А какой есть хороший (ну более-менее) набор готовых тестов для оценки сортировок?
Лучше что пока нашел — это "набора сортировок" от Christopher Swenson.
Взял исходники здесь и добавил в обозначенный выше бенчмарк.
Пришлось немного поправить:
- Вместо
intсортироватьint64_t, как в остальных сортировках в бенчмарке. - Увязать
delete[]иmalloc()в бенчмарке (он примерно на C):
- каждый
delete[] ptr=>if (pfr != malloced_array) delete[] ptr; - копировать отсортированный массив если он был перевыделен (да, это искажает результаты, но не принципиально).
- каждый
В сухом остатке у показанной сортировки:
- большие проблемы с low cardinality, до 1000 раз медленнее
- на случайных данных вдвое медленнее std::sort
- на упорядоченных данных часто примерно как timsort, иногда выигрывает в 2 раза, но местами проигрывает в 4-5-6 раз.
В самом бенчмарке я до этого уже добавил несколько тестов (вариантов распределения значений для сортировки) и две свои сортирующие функции (посмотреть можно тут).
gcc версия 9.2.1 20190827 (Red Hat 9.2.1-1) (GCC)
Целевая архитектура: x86_64-redhat-linux
CFLAGS = -Ofast -g -Wall -pedanticRunning tests with random:
extra.h yysort1_int64 - ok, 869995.0 usec
extra.h yysort2_int64 - ok, 900374.0 usec
extra.h sort_rela589n_int64 - ok, 1675713.0 usec
sort.h tim_sort - ok, 1629556.0 usec
sort.h quick_sort - ok, 1132862.0 usec
extra.h std_sort_int64 - ok, 999762.0 usec
extra.h std_stable_int64 - ok, 1285915.0 usec
sort.h heap_sort - ok, 1146402.0 usec
sort.h merge_sort - ok, 1503107.0 usec
sort.h shell_sort - ok, 2176027.0 usec
sort.h merge_sort_in_place - ok, 1463473.0 usec
sort.h grail_sort - ok, 1808871.0 usec
sort.h sqrt_sort - ok, 1515565.0 usec
stdlib qsort - ok, 2027280.0 usec
-------
Running tests with random 50% duplicates:
extra.h yysort1_int64 - ok, 860580.0 usec
extra.h yysort2_int64 - ok, 898808.0 usec
extra.h sort_rela589n_int64 - ok, 1669673.0 usec
sort.h tim_sort - ok, 1625739.0 usec
sort.h quick_sort - ok, 1120857.0 usec
extra.h std_sort_int64 - ok, 996282.0 usec
extra.h std_stable_int64 - ok, 1282137.0 usec
sort.h heap_sort - ok, 1140383.0 usec
sort.h merge_sort - ok, 1498133.0 usec
sort.h shell_sort - ok, 2147107.0 usec
sort.h merge_sort_in_place - ok, 1459049.0 usec
sort.h grail_sort - ok, 1810396.0 usec
sort.h sqrt_sort - ok, 1509897.0 usec
stdlib qsort - ok, 2040143.0 usec
-------
Running tests with random two values:
extra.h yysort1_int64 - ok, 253859.0 usec
extra.h yysort2_int64 - ok, 128689.0 usec
extra.h sort_rela589n_int64 - ok, 94094388.0 usec
sort.h tim_sort - ok, 452126.0 usec
sort.h quick_sort - ok, 115704.0 usec
extra.h std_sort_int64 - ok, 229533.0 usec
extra.h std_stable_int64 - ok, 362162.0 usec
sort.h heap_sort - ok, 580296.0 usec
sort.h merge_sort - ok, 525983.0 usec
sort.h shell_sort - ok, 485811.0 usec
sort.h merge_sort_in_place - ok, 434436.0 usec
sort.h grail_sort - ok, 611444.0 usec
sort.h sqrt_sort - ok, 544184.0 usec
stdlib qsort - ok, 811069.0 usec
-------
Running tests with random of 0..9:
extra.h yysort1_int64 - ok, 406745.0 usec
extra.h yysort2_int64 - ok, 315560.0 usec
extra.h sort_rela589n_int64 - ok, 7734804.0 usec
sort.h tim_sort - ok, 903047.0 usec
sort.h quick_sort - ok, 288444.0 usec
extra.h std_sort_int64 - ok, 386615.0 usec
extra.h std_stable_int64 - ok, 665899.0 usec
sort.h heap_sort - ok, 984863.0 usec
sort.h merge_sort - ok, 851956.0 usec
sort.h shell_sort - ok, 836794.0 usec
sort.h merge_sort_in_place - ok, 783045.0 usec
sort.h grail_sort - ok, 1697737.0 usec
sort.h sqrt_sort - ok, 881796.0 usec
stdlib qsort - ok, 1303944.0 usec
-------
Running tests with mixed-pattern (1/2 sorted, 1/6 reverse, 1/3 random):
extra.h yysort1_int64 - ok, 653220.0 usec
extra.h yysort2_int64 - ok, 709562.0 usec
extra.h sort_rela589n_int64 - ok, 708971.0 usec
sort.h tim_sort - ok, 646852.0 usec
sort.h quick_sort - ok, 885766.0 usec
extra.h std_sort_int64 - ok, 789911.0 usec
extra.h std_stable_int64 - ok, 625716.0 usec
sort.h heap_sort - ok, 1078595.0 usec
sort.h merge_sort - ok, 788254.0 usec
sort.h shell_sort - ok, 1972692.0 usec
sort.h merge_sort_in_place - ok, 678949.0 usec
sort.h grail_sort - ok, 979281.0 usec
sort.h sqrt_sort - ok, 769563.0 usec
stdlib qsort - ok, 1114687.0 usec
-------
Running tests with mixed-pattern 50% duplicates:
extra.h yysort1_int64 - ok, 651027.0 usec
extra.h yysort2_int64 - ok, 710886.0 usec
extra.h sort_rela589n_int64 - ok, 707473.0 usec
sort.h tim_sort - ok, 720871.0 usec
sort.h quick_sort - ok, 868391.0 usec
extra.h std_sort_int64 - ok, 785505.0 usec
extra.h std_stable_int64 - ok, 623365.0 usec
sort.h heap_sort - ok, 1075865.0 usec
sort.h merge_sort - ok, 794544.0 usec
sort.h shell_sort - ok, 1944434.0 usec
sort.h merge_sort_in_place - ok, 682350.0 usec
sort.h grail_sort - ok, 1044301.0 usec
sort.h sqrt_sort - ok, 771323.0 usec
stdlib qsort - ok, 1180723.0 usec
-------
Running tests with mixed-pattern two values:
extra.h yysort1_int64 - ok, 212801.0 usec
extra.h yysort2_int64 - ok, 90349.0 usec
extra.h sort_rela589n_int64 - ok, 70880347.0 usec
sort.h tim_sort - ok, 164127.0 usec
sort.h quick_sort - ok, 101332.0 usec
extra.h std_sort_int64 - ok, 182024.0 usec
extra.h std_stable_int64 - ok, 235439.0 usec
sort.h heap_sort - ok, 531226.0 usec
sort.h merge_sort - ok, 377192.0 usec
sort.h shell_sort - ok, 429685.0 usec
sort.h merge_sort_in_place - ok, 187419.0 usec
sort.h grail_sort - ok, 396649.0 usec
sort.h sqrt_sort - ok, 381190.0 usec
stdlib qsort - ok, 603217.0 usec
-------
Running tests with mixed-pattern of 0..9:
extra.h yysort1_int64 - ok, 301082.0 usec
extra.h yysort2_int64 - ok, 220010.0 usec
extra.h sort_rela589n_int64 - ok, 4049493.0 usec
sort.h tim_sort - ok, 327608.0 usec
sort.h quick_sort - ok, 193150.0 usec
extra.h std_sort_int64 - ok, 282951.0 usec
extra.h std_stable_int64 - ok, 348781.0 usec
sort.h heap_sort - ok, 928633.0 usec
sort.h merge_sort - ok, 492125.0 usec
sort.h shell_sort - ok, 653055.0 usec
sort.h merge_sort_in_place - ok, 343271.0 usec
sort.h grail_sort - ok, 944962.0 usec
sort.h sqrt_sort - ok, 517400.0 usec
stdlib qsort - ok, 787898.0 usec
-------
Running tests with sorted:
extra.h yysort1_int64 - ok, 140487.0 usec
extra.h yysort2_int64 - ok, 22329.0 usec
extra.h sort_rela589n_int64 - ok, 78184.0 usec
sort.h tim_sort - ok, 12440.0 usec
sort.h quick_sort - ok, 259474.0 usec
extra.h std_sort_int64 - ok, 187773.0 usec
extra.h std_stable_int64 - ok, 161101.0 usec
sort.h heap_sort - ok, 1001063.0 usec
sort.h merge_sort - ok, 294122.0 usec
sort.h shell_sort - ok, 349411.0 usec
sort.h merge_sort_in_place - ok, 28568.0 usec
sort.h grail_sort - ok, 390306.0 usec
sort.h sqrt_sort - ok, 240751.0 usec
stdlib qsort - ok, 469580.0 usec
-------
Running tests with sorted 93.75%:
extra.h yysort1_int64 - ok, 315492.0 usec
extra.h yysort2_int64 - ok, 332510.0 usec
extra.h sort_rela589n_int64 - ok, 688122.0 usec
sort.h tim_sort - ok, 527578.0 usec
sort.h quick_sort - ok, 667057.0 usec
extra.h std_sort_int64 - ok, 343515.0 usec
extra.h std_stable_int64 - ok, 422551.0 usec
sort.h heap_sort - ok, 1028983.0 usec
sort.h merge_sort - ok, 549670.0 usec
sort.h shell_sort - ok, 1811294.0 usec
sort.h merge_sort_in_place - ok, 614558.0 usec
sort.h grail_sort - ok, 816988.0 usec
sort.h sqrt_sort - ok, 669301.0 usec
stdlib qsort - ok, 930576.0 usec
-------
Running tests with reverse:
extra.h yysort1_int64 - ok, 272676.0 usec
extra.h yysort2_int64 - ok, 313761.0 usec
extra.h sort_rela589n_int64 - ok, 83115.0 usec
sort.h tim_sort - ok, 23235.0 usec
sort.h quick_sort - ok, 315033.0 usec
extra.h std_sort_int64 - ok, 184726.0 usec
extra.h std_stable_int64 - ok, 251171.0 usec
sort.h heap_sort - ok, 953360.0 usec
sort.h merge_sort - ok, 401169.0 usec
sort.h shell_sort - ok, 496127.0 usec
sort.h merge_sort_in_place - ok, 323996.0 usec
sort.h grail_sort - ok, 479127.0 usec
sort.h sqrt_sort - ok, 257342.0 usec
stdlib qsort - ok, 535662.0 usec
-------
Running tests with 111......000:
extra.h yysort1_int64 - ok, 164210.0 usec
extra.h yysort2_int64 - ok, 20986.0 usec
extra.h sort_rela589n_int64 - ok, 94005419.0 usec
sort.h tim_sort - ok, 17461.0 usec
sort.h quick_sort - ok, 44549.0 usec
extra.h std_sort_int64 - ok, 135267.0 usec
extra.h std_stable_int64 - ok, 171308.0 usec
sort.h heap_sort - ok, 496364.0 usec
sort.h merge_sort - ok, 300909.0 usec
sort.h shell_sort - ok, 359109.0 usec
sort.h merge_sort_in_place - ok, 61315.0 usec
sort.h grail_sort - ok, 258391.0 usec
sort.h sqrt_sort - ok, 309822.0 usec
stdlib qsort - ok, 489699.0 usec
-------
Running tests with 999..., 888..., ..., ...000:
extra.h yysort1_int64 - ok, 163028.0 usec
extra.h yysort2_int64 - ok, 21040.0 usec
extra.h sort_rela589n_int64 - ok, 33905532.0 usec
sort.h tim_sort - ok, 34008.0 usec
sort.h quick_sort - ok, 99381.0 usec
extra.h std_sort_int64 - ok, 139307.0 usec
extra.h std_stable_int64 - ok, 176955.0 usec
sort.h heap_sort - ok, 859782.0 usec
sort.h merge_sort - ok, 312193.0 usec
sort.h shell_sort - ok, 372891.0 usec
sort.h merge_sort_in_place - ok, 109063.0 usec
sort.h grail_sort - ok, 473525.0 usec
sort.h sqrt_sort - ok, 355316.0 usec
stdlib qsort - ok, 513460.0 usec
-------
Running tests with all same:
extra.h yysort1_int64 - ok, 167847.0 usec
extra.h yysort2_int64 - ok, 21873.0 usec
extra.h sort_rela589n_int64 - ok, 78372.0 usec
sort.h tim_sort - ok, 12293.0 usec
sort.h quick_sort - ok, 18023.0 usec
extra.h std_sort_int64 - ok, 137651.0 usec
extra.h std_stable_int64 - ok, 161931.0 usec
sort.h heap_sort - ok, 68188.0 usec
sort.h merge_sort - ok, 292633.0 usec
sort.h shell_sort - ok, 348899.0 usec
sort.h merge_sort_in_place - ok, 28329.0 usec
sort.h grail_sort - ok, 207439.0 usec
sort.h sqrt_sort - ok, 255837.0 usec
stdlib qsort - ok, 459560.0 usec
-------
Running tests with sorted blocks of length 10:
extra.h yysort1_int64 - ok, 831530.0 usec
extra.h yysort2_int64 - ok, 868527.0 usec
extra.h sort_rela589n_int64 - ok, 1670283.0 usec
sort.h tim_sort - ok, 1516381.0 usec
sort.h quick_sort - ok, 1083222.0 usec
extra.h std_sort_int64 - ok, 961874.0 usec
extra.h std_stable_int64 - ok, 1134245.0 usec
sort.h heap_sort - ok, 1128264.0 usec
sort.h merge_sort - ok, 1339936.0 usec
sort.h shell_sort - ok, 2029549.0 usec
sort.h merge_sort_in_place - ok, 1314025.0 usec
sort.h grail_sort - ok, 1688303.0 usec
sort.h sqrt_sort - ok, 1383832.0 usec
stdlib qsort - ok, 1808273.0 usec
-------
Running tests with sorted blocks of length 100:
extra.h yysort1_int64 - ok, 698704.0 usec
extra.h yysort2_int64 - ok, 737751.0 usec
extra.h sort_rela589n_int64 - ok, 1664662.0 usec
sort.h tim_sort - ok, 842203.0 usec
sort.h quick_sort - ok, 952365.0 usec
extra.h std_sort_int64 - ok, 832443.0 usec
extra.h std_stable_int64 - ok, 832485.0 usec
sort.h heap_sort - ok, 1100130.0 usec
sort.h merge_sort - ok, 992872.0 usec
sort.h shell_sort - ok, 1722663.0 usec
sort.h merge_sort_in_place - ok, 1054561.0 usec
sort.h grail_sort - ok, 1375290.0 usec
sort.h sqrt_sort - ok, 1088504.0 usec
stdlib qsort - ok, 1415336.0 usec
-------
Running tests with sorted blocks of length 10000:
extra.h yysort1_int64 - ok, 361783.0 usec
extra.h yysort2_int64 - ok, 429301.0 usec
extra.h sort_rela589n_int64 - ok, 309345.0 usec
sort.h tim_sort - ok, 153956.0 usec
sort.h quick_sort - ok, 658700.0 usec
extra.h std_sort_int64 - ok, 492720.0 usec
extra.h std_stable_int64 - ok, 280025.0 usec
sort.h heap_sort - ok, 1027617.0 usec
sort.h merge_sort - ok, 413609.0 usec
sort.h shell_sort - ok, 725664.0 usec
sort.h merge_sort_in_place - ok, 370757.0 usec
sort.h grail_sort - ok, 642283.0 usec
sort.h sqrt_sort - ok, 438289.0 usec
stdlib qsort - ok, 664060.0 usec
-------
Running tests with swapped size/2 pairs:
extra.h yysort1_int64 - ok, 749093.0 usec
extra.h yysort2_int64 - ok, 778670.0 usec
extra.h sort_rela589n_int64 - ok, 1602673.0 usec
sort.h tim_sort - ok, 1356477.0 usec
sort.h quick_sort - ok, 1042425.0 usec
extra.h std_sort_int64 - ok, 857866.0 usec
extra.h std_stable_int64 - ok, 1045840.0 usec
sort.h heap_sort - ok, 1123542.0 usec
sort.h merge_sort - ok, 1233686.0 usec
sort.h shell_sort - ok, 2143031.0 usec
sort.h merge_sort_in_place - ok, 1253314.0 usec
sort.h grail_sort - ok, 1547192.0 usec
sort.h sqrt_sort - ok, 1259113.0 usec
stdlib qsort - ok, 1721907.0 usec
-------
Running tests with swapped size/8 pairs:
extra.h yysort1_int64 - ok, 421713.0 usec
extra.h yysort2_int64 - ok, 449412.0 usec
extra.h sort_rela589n_int64 - ok, 969430.0 usec
sort.h tim_sort - ok, 749844.0 usec
sort.h quick_sort - ok, 753447.0 usec
extra.h std_sort_int64 - ok, 460800.0 usec
extra.h std_stable_int64 - ok, 563436.0 usec
sort.h heap_sort - ok, 1054573.0 usec
sort.h merge_sort - ok, 706547.0 usec
sort.h shell_sort - ok, 1947799.0 usec
sort.h merge_sort_in_place - ok, 783277.0 usec
sort.h grail_sort - ok, 986328.0 usec
sort.h sqrt_sort - ok, 803845.0 usec
stdlib qsort - ok, 1112677.0 usec
-------
Running tests with known evil data (odd/even hi/low swap):
extra.h yysort1_int64 - ok, 153238.0 usec
extra.h yysort2_int64 - ok, 105138.0 usec
extra.h sort_rela589n_int64 - ok, 145879.0 usec
sort.h tim_sort - ok, 305719.0 usec
sort.h quick_sort - ok, 515508.0 usec
extra.h std_sort_int64 - ok, 169849.0 usec
extra.h std_stable_int64 - ok, 243750.0 usec
sort.h heap_sort - ok, 984348.0 usec
sort.h merge_sort - ok, 403293.0 usec
sort.h shell_sort - ok, 624925.0 usec
sort.h merge_sort_in_place - ok, 431592.0 usec
sort.h grail_sort - ok, 675009.0 usec
sort.h sqrt_sort - ok, 380917.0 usec
stdlib qsort - ok, 707122.0 usecrela589n, вы видели эти результаты?
Ну, честно могу сказать, что это лучше, чем "Воронки", тут хотя бы есть код реализации чтобы можно было объективно сравнивать.
1) аллокация памяти — зло. Если массив будет размером с гигабайт, получается вы ещё два выделяете? Это в принципе может как затормозить весь процесс, так и просто тут же вывалить bad_alloc
2) Данные бывают абсолютно разные, не только случайные или упорядоченные. Как поведёт себ алгоритм, если данные лежат в обратном порядке, если равны, чередуются с нулем и 1… Много вариантов, и на самом деле все это может непредсказуемо работать по времени. И если вы соревнуетесь с библиотечной версией sort, то должны и их протестировать.
Кстати у Александреску в этом году на cppcon как раз была про это лекция, как он сортировку улучшал (https://youtu.be/FJJTYQYB1JQ)
Здесь всё принципиально от дополнительной памяти зависит. Например алгоритм красно-чёрного дерева позволяет добавлять в сортированное дерево новый элемент (оставляя его сортированным) за O(log(N)) операций. Откуда получим уже сложность O(n*log(N)).
Также есть алгоритм работающий за O(M) операций (M — количество возможных значений в диапазоне значений), но при условии, что диапазон значений ограничен:
1) Присваиваем каждой сущности из диапазона своё число от 1 до M в порядке возрастания
2) Создаём массив из M значений
3) Записываем в этот массив по индексу, равному соответствующему сущности числу (на случай коллизий можно, например, списки по индексу хранить — так как порядок одинаковых значений не важен)
Особенно хорошо работает с короткими диапазонами и большим количеством элементов.
Если сортируются числа — ещё удобнее (вместо списков можно количество записывать)
Сортировка выбором минимумов (максимумов)