Jump to content

    
Sign in to follow this  
sigmaN

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

Recommended Posts

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

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Sign in to follow this