Потому что worst-case space complexity: O(n).

Quicksort хорош именно тем, что памяти жрет O(log n). Это две разные категории алгоритмов: одни стабильные (как mergesort), другие к памяти нетребовательные (у heapsort, кстати, худшее время лучше, чем у quicksort - но в среднем он медленнее). Для разных, соответственно, задач. Предложение заменить одно другим так же странно, как предложение заменить jpeg на mp3.

Вот придумал бы кто стабильный in-place алгоритм, да с худшим временем O(log n), да еще и с нормальной константой - вот тогда зажили бы. Но не придумывают же ни хуя. Чаи гоняют в своих институах, по конференциям анекдотики-хуетики рассказывают, а мы блядь ебись а алгоритмами сороковых годов. Думают, что если они PhD в Computer Sience, то можно говном на нас срать. Нейронные блядь сети вместо нормальных алгоритмов выдумывают, а как пахать - так мы. А я на фортране прграммировал, и я не позволю над собой так издеваться. Квантовые алгоритмы, а я их гадов ебал.

(Reply to this) (Thread)

да ладно, тимсорт требует где-то чуть больше килобайта дополнительной памяти под стек этих… как их… runs. совершенно не то, на что стоит обращать внимание во всяких там libc. а если начать улучшать квиксорт на предмет толерантности к «плохим данным», то он тоже начинает или памяти требовать, или замедляется «в общем случае». с тимсортом получаем не медленней, зато мегавин на partially sorted, да ещё и stable. не вижу никакой причины не заменить реализацию qsort на тим.

и да: даже усложнённые варианты квиксорта намного проще в реализации, чем тим. поэтому кому реально надо квик — это пол-экрана кода. а тим заебёшься писать и отлаживать. поэтому я считаю, что в библиотеку — тим. а квик пусть носит кому надо.

(Reply to this) (Parent) (Thread)

Стек, если я правильно понимаю, там нужен только на три run'а - перед тем, как сунуть туда следующий, какие-то два объединяются. Это, действительно, байты.

А вот для того, чтобы смержить два массива, может понадобиться дополнительная память размером с один из них. И если так сложится, что на последнем этапе будет два run'а по гигабайту каждый - то придется где-то брать гигабайт дополнительной памяти.

Частично упорядоченные массивы - это какой-то фантастический случай, честно говоря. Я только один реальный сценарий этого вижу: нам надо поддерживать отсортированный массив каких-то величин, а эти величины продолжают откуда-то поступать. Мы дописываем вновь полученные данные в конец массива, и запускаем тимсорт. Вот тогда заебись будет, любой другой алгоритм соснет.

Только вот умный человек так делать не будет, он отсортирует новые данные (не важно, чем - их все равно мало), а затем смержит два отсортированных массива (причем поскольку в первом массиве уже должно быть место под дополнительные элементы, то нам даже память выделять как бы и не понадобится).

Так что на мой вкус тимсорт - это что-то для питонобыла ебаного, которое сортирует одно и то же по пятьсот раз подряд, потому что не понимают вообще нихуя, Кнута не читали, пидоры сраные, а лезут программировать. Дай им квиксорт - они и его поломают, и хуй себе изрежут.

(Reply to this) (Parent) (Thread)

>А вот для того, чтобы смержить два массива, может понадобиться дополнительная
>память размером с один из них
ну, там размеры run-ов ограничены (макс. 64, вроде бы), так что если не сортировать массивы, где элементы размерами в мегабайты, то тоже слёзки. алсо, по-моему, есть вариант почти-in-place mergesort. который, конечно, медленней, но если у тебя огромного размера элементы — то вполне вариант переключиться на него. как раз в духе адаптивности тимсорта будет.

>Частично упорядоченные массивы - это какой-то фантастический случай, честно
>говоря
да влёт. в спелунке, например, каждый спрайт имеет depth, по которой спрайты и сортируются перед рендером. и большинство спрайтов вообще одинаковый depth имеют, а у остальных часто встречается ситуация упорядоченности, когда несколько объектов друг на дружке. реально, быстрее их сложить в массив и потом отсортировать, чем двигать куски массива туда-сюда, вставляя в нужное место.

и подобные ситуации встречаются нередко. ирл большинство «рандомных» данных имеют достаточно большие отсортированые куски (потому что данные на самом деле нифига не рандомные жы).

в итоге тимсорт немного жертвует памятью (но нефатально, особенно на современной технике), зато амортизирует весьма часто встречающиеся ирл случаи. плюс — я таки могу и не думать ни о том, что у меня есть вариант, когда программа ВНИЗАПНА просядет нафиг, и делать сортировки по нескольким ключам в несколько же проходов без боязни всё поломать (stable жы). второе не так глупо, как кажется: весьма полезно в UI, где данные можно сортировать/фильтровать по нескольким разным критериям.

(Reply to this) (Parent) (Thread)

Не-не-не, размеры run'ов ограничены СНИЗУ - куски, меньшие 64 элементов сортируются вставками. А сверху предела нет - run'ы объединяются друг с другом, их размер растет. Если все хорошо, то мы все время к большому куску прибавляем маленький (и нам нужна дополнительная память размером с маленький кусок). Но если что-то пойдет не так, то в конце мы будем иметь два здоровых куска в половину массива каждый. То есть обязательно внезапно просядет, хотя и не по времени. В некоторых задачах это не критично (то есть заранее известно, что объем свободной памяти больше сортируемых массивов), но как универсальное решение это не годится.

In-place merge либо не in-place, либо не O(n).

Mergesort ничем не лучше timsort, те же проблемы с памятью, только без плюшек на особых случаях. Собственно, timsort - это и есть mergesort, заоптимизированный под особые случаи.

Что касается примера со спрайтами - Если я правильно понял, там есть статические элементы (более-менее упорядоченные) и динамические, которые из-за своей динамичности не упорядочены? Тогда тоже лучше всю статику упорядочить один раз на всю жизнь, а динамику сортировать отдельно после каждого изменения, затем мержить за O(n).

Ну и вообще - если данные не рандомны, то лучше понять, в чем там закономерность и эксплуатировать ее сознательно. Быстрее будет. А сама идея сделать алгоритм, который с одной стороны универсальный, а с другой - оптимизирован под некие "часто встречающиеся случаи" отдает ебучими нейронными сетями, которые дают правильный ответ, но не всегда, а только с большой вероятностью.

Сортировки в несколько проходов по разным ключам - да, это нормально, особенно если порядок сортировки известен только на рантайме, и захардкодить сравнение по составному ключу нельзя. Но если сортируются сами объекты, а не индексы, то, возможно, лучше иметь очень сложную (и медленную) функцию сравнения, чем двигать объекты по памяти в несколько раз чаще.

(Reply to this) (Parent) (Thread)

>А сверху предела нет - run'ы объединяются друг с другом, их размер растет.
ок, может быть. я не очень вникал — взял готовое и всё откладываю подробно разобраться.

>In-place merge либо не in-place, либо не O(n).
да, он не совсем O(n). но для огромных кусков вполне есть смысл — там всё равно движение памяти уже слопает порядочно скорости, так что особого смысла пытаться выиграть за счёт strict time нет. мне так кажется.

>Тогда тоже лучше всю статику упорядочить один раз на всю жизнь, а динамику
>сортировать отдельно после каждого изменения, затем мержить за O(n).
там в принципе нет «статики» — там любой объект потенциально динамический. это во-первых. во-вторых, обработка всех объектов одинаковым кодом упрощает этот самый код. в третьих, динамику же всё равно надо в середину статики вставлять: что-то прячется за определённые виды тайлов, что-то нет. в итоге всё равно надо сливать массивы — так зачем изобретать спецалгоритмы (и потом захардкоживать этот отдельный случай в универсальную исполнялку), если можно тупо отсортировать. тут баланс между усложнением кода путём вписывания спецслучаев, и: «да похеру, пусть сортирует, зато код простой как полено.»

изначально в спелунке примерно так и было: несколько гридов даже для разных объектов. а потом я заебался и слил всё в кучу. проебал где-то один процент CPU в итоге, зато выкинул кучу хрупких условий.

опять же, уровень в спелунке разрушаемый и изменяемый, так что проще считать тайлы просто такими же объектами, как и всё остальное.

>если данные не рандомны, то лучше понять, в чем там закономерность и
>эксплуатировать ее сознательно. Быстрее будет.
иногда да. а иногда проще воткнуть алгоритм, который «более-менее справляется» и забить. но беда в том, что в стдлибе такого алгоритма нет — поэтому приходится таскать с собой копипасту.

>А сама идея сделать алгоритм, который с одной стороны универсальный, а с другой -
>оптимизирован под некие "часто встречающиеся случаи" отдает ебучими
>нейронными сетями, которые дают правильный ответ, но не всегда, а только с
>большой вероятностью.
ну да, адаптивные алгоритмы — те ещё банки с червями, конечно. к тому же в них часто эвристики адаптивности взяты или вообще от фонаря, или под технику того времени, когда они создавались, и могут давно уже сосаеть.

я, пожалуй, погорячился с требованием замены. а вот добавить тимсорт в libc, например — это было бы вполне в тему. хоть и раздувание и без того дурных размеров библиотеки, но иметь выбор между «быстрым, но не очень толерантным к сортированым данным» и «не таким быстрым, но хорошо жующим сортированое, да ещё и стабильным» — было бы очень неплохо. хотя бы для того, чтобы люди не таскали с собой разные реализации не самого тривиального алгоритма.

(Reply to this) (Parent)

p.s.: понятно, что описаные в последнем абзаце случаи можно заворкэраундить разными методами, но нафига, если есть сортировщик, который нормально справляется без хаков?

(Reply to this) (Parent)

p.s.: но если мне надо вдруг зачем-то написать сортировку без стдлиба, то я обычно таки хипсорт сую. потому что «херовые данные» таки встречаются намного чаще, чем кажется, и ну его — пусть лучше в среднем чуть медленней, чем ВНИЗАПНО просядет.

(Reply to this) (Parent) (Thread)

Подход разумного человека, я считаю. Надежность и стабильность важнее скорости, да и не такая там большая разница в средней скорости, что бы было о чем жалеть.

(Reply to this) (Parent)