Sorting array with constant memory

Given an array of length $n$ we need at least $O(\log n)$ memory to store its length. And we need the same $O(\log n)$ memory to store index. With large $n$, index may not fit in one extra cell.

So it is impossible to construct a sorting algorithm for arrays which uses $O(1)$ additional memory.

On the other hand, one can construct sorting algorithm for some other sequence, e.g. list. This can be modification of bubble sort (or cocktail sort). Something like this:

1. goto head, set flag to false
2. if current element is bigger than next, swap and set flag to true
3. if there is no next element and flag is true, goto 1
4. if there is no next element and flag is false, end

So this algorithm uses only two extra cells: one for flag and one for swap.

Am I missing something or am I right and it is impossible to construct a sorting algorithm for arrays with constant memory?

• I'm not sure what your model is. If you're counting the cost of an index into the array as non-constant then, presumably, you'd also count the cost of a pointer in a linked list as non-constant. If so, that seems to rule out almost any approach: how do you go to the next element without reading in a non-constant amount of pointer data, for example? – David Richerby Dec 3 '14 at 12:40
• Thanks, I missed the obvious thing that for any addressing we need logarithmic memory. How about some sequence bounded with special symbols and slightly modified algorithm going forwards and backwards? – ov7a Dec 3 '14 at 14:24