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

S>Здравствуйте, Аноним, Вы писали:

А>>А расскажите как вы отсортируете за O(n log n) времени, при O(1) памяти.

S>См. пирамидальную сортировку.

S>Хотя с точки зрения практики O(log n) весьма недалеко от O(1). Возникают даже всякие вопросы, типа того, что индексная переменная, которая бегает по массиву, тоже занимает не менее O(log n) памяти.

Как одна переменная может занимать logn памяти без использования рекурсии? Массив что ли?