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

EP>В статье, ссылку на которую я привёл, вообще описывается явный стек (nest). Существенным моментом здесь является не tail-call сам по себе, а гарантия лографмического размера — вполне алгоритмическая черта.

Quicksort, описанный во многих книжках по алгоритмике с O(n) памяти — это не Quicksort тогда, так? Ну и, конечно же, stable версии алгоритма тогда не существует.

EP>Применение Lomuto partition для подобной сортировки — это крайне нерационально. Степанов объяснил почему — получается крайне неэффективно, так как намного чаще вырождается в квадратичность.

Честно говоря, Степанов произнес там какую-то наивную речь. Типа не протестировали, не обратили внимание. Код с Lomuto partition имеет очевидные проблемы, это всем понятно (уж людям уровня авторов CLRS так точно). Так же, как и любая другая реализация Quicksort, каждая со своими проблемами, поэтому в нормальных библиотеках и используют introsort.