[sigmaN 0]

5 hours ago, xvr said:

в 2 раза медленнеё стандартного quicksort'а. Тогда зачем она?

Алгоритм merge sort не корректно сравнивать с quick sort потому как merge - это стабильная сортировка(сортировка, которая не меняет относительный порядок сортируемых элементов, имеющих одинаковые ключи). quick таким свойством не обладает.
Ответ на вопрос зачем можно встретить уже в названии топика. Ну и далее я на него неоднократно отвечал.

[xvr 12]

18 hours ago, sigmaN said:

Алгоритм merge sort не корректно сравнивать с quick sort потому как merge - это стабильная сортировка

Ну так std::stable_sort тоже быстрее :(

18 hours ago, sigmaN said:

Ответ на вопрос зачем можно встретить уже в названии топика.

Даже 2. Первый про 'нерекурсивная'. Очень спорное преимущество. Скорости это не прибавляет, как мы видели. А экономия стека на вызовы имеет смысл там, где этот стек сильно ограничен - а на таких архитектурах вопрос о обработке стомегебайтных массивов в принципе не стоит.

 

Второй 'чисто спортивный интерес'. Тогда это этюд в стиле олимпиады по програмированию :)

А изучать влияние кэшей (3я причина, которая была 'неоднократно отвечена') лучше на других примерах, там где их влияние гораздо сильнее (я уже говорил - умножение матриц. Это задача 2х мерная, поэтому простым переупорядочиванием она не решается)

[sigmaN 0]

7 hours ago, xvr said:

Ну так std::stable_sort тоже быстрее :(

Не так драматически.

7 hours ago, xvr said:

ервый про 'нерекурсивная'. Очень спорное преимущество. Скорости это не прибавляет, как мы видели.

Не знаю как это мы видим? )) Лично у меня классическая рекурсивная реализация проигрывает как по скорости, так и по требуемой памяти. И вообще считаю, что если есть требования к скорости и есть возможность что-то реализовать не рекурсивно - нужно реализовывать не рекурсивную версию.

Но да ладно, перейдем к делу.
Вчера вернулся я к этой задаче. Думал, гадал... туда-сюда код вертел... Ускорения особого добиться не удалось.
Сдаюсь, думаю. Пойду смотреть как stable_sort реализован в STL.

Входная последовательность разбивается на группы по 32 элемента
Каждая такая группа сортируется сортировкой вставкой(insertion sort)
После этого начинаются объединения(merge)

Так что стало ясно, что алгоритм просто другой. Я "по честному" сливаю всё начиная от групп по 1 элемента, а там всё начинается с групп по 32.

Еще потом посмотрю, может мелкомягкие еще какие-то хитрости используют ))

 

[sigmaN 0]

https://youtu.be/FJJTYQYB1JQ

Годный доклад Александреску 2019 года по поводу сортировки. В том числе рассматриваются реализации std::sort в разных библиотеках.

Add: ему удалось превзойти std::sort! Довольно неожиданным способом. В общем, Александреску в очередной рвз не подвёл ))