I know most people use quick sort to solve this problem. But in fact the space complexity of the quick sort should be *O(nlogn)* because of the stack allocation(such as the return address pushed in the stack, local variables you used in recursion function).

Actually, any divide-and-conquer approaches (like merge sort *even for the in-place merge implementation*, quick sort) for this problem requires more than constant memory. Without divide-and-conquer approach, the only way I know for sorting in O(nlogn) time is heap sort. Unfortunately, this solution is even worse than divide-and-conquer approach.

There is some algorithm uses constant memory space like bubble sort, insertion sort ,etc. But the time complexity of none of them are O(nlogn).

So I feel so confused about this, Is there any sorting algorithm we can use here to get a real constant memory complexity? But it seems impossible to me, so does anyone have ideas about this?