Jump to content

    

Нерекурсивная сортировка слиянием(merge sort). Чисто спортивный интерес.

5 hours ago, xvr said:

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

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

Share this post


Link to post
Share on other sites
18 hours ago, sigmaN said:

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

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

18 hours ago, sigmaN said:

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

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

 

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

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

Share this post


Link to post
Share on other sites
7 hours ago, xvr said:

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

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

7 hours ago, xvr said:

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

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



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

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

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

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

 

Share this post


Link to post
Share on other sites

https://youtu.be/FJJTYQYB1JQ

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

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

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now