Merge Sort без рекурсии

[Andrey_Kireew]

Здравствуйте уважаемые участники форума.
Разбираюсь с алгоритмами сортировки, пытаюсь найти для себя оптимальный вариант.
Алгоритм Merge Sort в этом плане выгодно отличается от других, имея гарантированную сложность $O(n\cdot log(n)$. Но он реализуется рекурсивно. Это мне не очень нравится. Могут возникнуть проблемы с устойчивостью, да и рекурсия плохо укладывается у меня в голове.

Собственно вопрос - можно ли в принципе реализовать Merge Sort, без рекурсии? Известны ли такие реализации?

[mihaild]

Andrey_Kireew в сообщении #1328534 писал(а):

Могут возникнуть проблемы с устойчивостью

Что вы здесь понимаете под устойчивостью?

Вообще, никто не мешает завести стек руками и реализовать рекурсивные вызовы через цикл. Смысл этого, правда, не очень понятен.

[Geen]

Andrey_Kireew
А Вы википедию смотрели?

И заодно посмотрите smoothsort (плавная сортировка)...

[Andrey_Kireew]

Geen в сообщении #1328537 писал(а):

Andrey_Kireew
А Вы википедию смотрели?

конечно, куда же сейчас без неё :)

про smoothsort - спасибо, почитаю!

но мой вопрос вообще имеет свои корни: "порывшись" в своих исходниках - нашел там, среди прочих, Merge Sort, код небольшой, примерно как и в "Вики" по объёму, но в нём нет никакой рекурсии. Я подумал, что недоработанный - проверил - работает. Сравнил со скоростью sort из matlab на 10000000 случайных семплах - скорость примерно сопоставимая (Shell Sort при этом проигрывает в 200 раз).

[Geen]

Andrey_Kireew в сообщении #1328542 писал(а):

конечно, куда же сейчас без неё :)

Так там же описано как реализовать без рекурсии...

Andrey_Kireew в сообщении #1328542 писал(а):

Сравнил со скоростью sort из matlab на 10000000 случайных семплах

Помниться, у меня smoothsort обгонял на больших и примерно отсортированных массивах... (кажется, по крайней мере тогда, MatLab использовал быструю сортировку)

[Andrey_Kireew]

Geen в сообщении #1328546 писал(а):

Так там же описано как реализовать без рекурсии...

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

[iifat]

Andrey_Kireew в сообщении #1328534 писал(а):

проблемы с устойчивостью

На всякий случай: если под устойчивостью понимается устойчивость сортировки, то она не зависит от рекурсии/итерации. Только от алгоритма. И, кстати, как пирамидальная, так и, подозреваю, smoothsort неустойчивы.

[Geen]

iifat в сообщении #1328551 писал(а):

smoothsort неустойчивы.

Да, неустойчива.
Но любую неустойчивую можно сделать устойчивой добавлением к ключу сравнения индекса в исходном массиве. Но если надо "синхронно" переупорядочить несколько массивов сортируя один из них, то это даже "бесплатно"

[Sender]

Есть ещё timsort, она, если не изменяет память, устойчива.

[Andrey_Kireew]

Да нет, под устойчивостью я подразумевал не сохранение порядка, а что то ближе к тому, о чём упомянул mihaild.

[mihaild]

Я вроде бы ничего не упоминал в этом смысле. По крайней мере, что вы понимаете под устойчивостью, я до сих пор не понимаю.

[Dmitriy40]

Возможно подразумевалась глубина стека рекурсии в зависимости от размера и содержимого сортируемого массива. Но смысл её точной оценки и постоянства непонятна, обычно достаточно оценить сверху (это просто) и всё, мало кого волнует выделить 1К или 10К памяти (я так вообще на цифры расхода памяти до единиц мегабайтов внимания не обращаю ).

[Geen]

Sender в сообщении #1328559 писал(а):

Есть ещё timsort, она, если не изменяет память, устойчива.

Да, но не нравятся мне в нём эвристики...

(и особенно "радует" упоминание о том, что три его имплементации работали некорректно )

[iifat]

Краше цифровой всё равно нету