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

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

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

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