Здравствуйте, Qbit86, Вы писали:

EP>>Оригинальный quicksort помимо inplace ещё и ограничивает глубину стэка логарифмом.
Q>Оригинальный QuickSort как раз не ограничивает глубину вызовов, поэтому она может вырождаться до эн,

Ограничивает глубину стэка логарифмом. Это явно описано в оригинальной статье Хоара.
И я уже это подробно объяснял:

EP>Здравствуйте, Qbit86, Вы писали:

Q>>>Быструю сортировку можно и без рекурсивных вызовов организовать, эмулировав стек, но так обычно не делают в стандартных библиотеках. То есть почему-то не спешат менять потенциальный StackOverflowEcxeption на потениальный OutOfMemoryException. Добавляют при необходимоти guard глубины рекурсии, и живут себе, поди, без штрафов к премиям.

EP>Справедливости ради, в нормальной quicksort глубина стэка гарантированно ограничена O(ln(N)), в worst case.
EP>Там внутри две рекурсии — по левой стороне массива и по правой. Для той у которой размер массива больше — делают ручной tail call. То есть рекурсия происходит всегда в меньшую сторону, причём это может быть как левая, так и правая сторона.
EP>Размер меньшей части гарантированно меньше половины размера исходного массива, то есть рекурсия как минимум делится пополам, что гарантирует логарифмическую глубину.

Q>и общая сложность в худшем случае деградирует до эн-квадрат.

Глубина стэка != сложность алгоритма.

Здравствуйте, Qbit86, Вы писали:

EP>>Оригинальный quicksort помимо inplace ещё и ограничивает глубину стэка логарифмом.
Q>Оригинальный QuickSort как раз не ограничивает глубину вызовов, поэтому она может вырождаться до эн,

Ограничивает глубину стэка логарифмом. Это явно описано в оригинальной статье Хоара.
И я уже это подробно объяснял

Автор: Evgeny.Panasyuk
Дата: 22.05.15

:

EP>Здравствуйте, Qbit86, Вы писали:

Q>>>Быструю сортировку можно и без рекурсивных вызовов организовать, эмулировав стек, но так обычно не делают в стандартных библиотеках. То есть почему-то не спешат менять потенциальный StackOverflowEcxeption на потениальный OutOfMemoryException. Добавляют при необходимоти guard глубины рекурсии, и живут себе, поди, без штрафов к премиям.

EP>Справедливости ради, в нормальной quicksort глубина стэка гарантированно ограничена O(ln(N)), в worst case.
EP>Там внутри две рекурсии — по левой стороне массива и по правой. Для той у которой размер массива больше — делают ручной tail call. То есть рекурсия происходит всегда в меньшую сторону, причём это может быть как левая, так и правая сторона.
EP>Размер меньшей части гарантированно меньше половины размера исходного массива, то есть рекурсия как минимум делится пополам, что гарантирует логарифмическую глубину.

Q>и общая сложность в худшем случае деградирует до эн-квадрат.

Глубина стэка != сложность алгоритма.