What is the most efficient constant-space sorting algorithm? I'm looking for a sorting algorithm for int arrays that doesn't allocate any byte other than the size of the array, and is limited to two instructions:


SWAP: swap the next index with the current one;
MOVE: moves the cursor to +1 or -1 index;


That is, you can't swap non neighboring indexes, nor swap the index 100, after you just swapped index 10. What is the most efficient algorithm - i.e., the one that uses the less amount of total moves?
Consider cocktail shaker sort, which is a bidirectional version of bubble sort.  You bubblesort from low to high, and then (this is the added part) you bubblesort from high to low, repeat until done.  This is still $O(n^2)$, but it makes significantly fewer passes on average, because small elements near the high end of the array will be moved to their final position in a single pass rather than N passes.  Also, you can keep track of the lowest and highest positions where a swap occurred; subsequent passes need not scan beyond those points.