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 false2. if current element is bigger than next, swap and set flag to true3. if there is no next element and flag is true, goto 14. if there is no next element and flag is false, endSo 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? 
Sorting array with constant memory
complexity theory;sorting;space complexity