Не-не-не, размеры 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)