# 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:

1. SWAP: swap the next index with the current one;

2. 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?

-
Not that strange, it is a physical machine which will sort a list of carts glued to a looong tape that is rolled up. The machine can only move the the tape forward or backward, and can only swap neighboring cards, of corse. In the real world you can't teleport around, so, those are the restrictions... – srvm Mar 28 at 12:43
So, when you say that you want an algorithm that doesn't allocate any byte other than the size of the array, I guess you refer only to element storage, right? I can still allocate counters and such? – Darkhogg Mar 28 at 12:46
Oh, sure. Of course. You can alloc some additional structures. You can even alloc the whole array and do a lot of really heavy computation and that counts as 0 cost. The only thing you need to minimize is the number of SWAP/MOVEs of the actual physical machine, because it is slow. Bubble sort is the best I could came up with, but I guessed there should be better options. – srvm Mar 28 at 12:49
I don't think there is such an algorithm. Without any extra memory, you'll have no way to store any control state. – Raphael Mar 28 at 13:13
@svrm: yeah, then with unlimited RAM and the ability to copy the tape into RAM and do arbitrary computation on it for free, the algorithm "try everything and apply the best" is optimal in terms of number of moves of the tape. Unlikely to be practical, but that's because in practice the runtime would be squillions of years, not 0 ;-) If it costs N moves to copy a tape of length N into RAM, then naive brute force might not be optimal but it's within N of optimal. But none of this is specific to your problem: many problems when stated this way could be solved "offline" using a bogus algorithm. – Steve Jessop Mar 29 at 13:07

The sort you want is gnome sort.

The bubble sort algorithm is:

Run over the entire list from left to right.
At every point in the list, are the current item and next item out of order?
Yes: swap them and remember you made a swap.
No: ignore them.
Did you make any swaps while running over the list?
No: The list is sorted
Yes: Start over from the leftmost item.


The gnome sort algorithm assumes that the gnome begins at the leftmost end of the list. It proceeds:

Step one: Are you past the right end of the list?
Yes: The list is sorted
No: Continue onto the next step.

Step two: Evaluate these two questions:
(1) Are you at the leftmost item?
(2) Are you not at the leftmost item, and the current item
and the item to your left are in order?
Both no:
Swap the current item with the item to your left.
Take a step to the left.
Run step two again.
Either yes:
Take a step to the right.
Go back to step one.


Gnome sort is superior to bubble sort in that the only state you must remember is the current position of the gnome. Whereas with bubble sort you must remember not only the current position, but whether or not you did any swaps in the pass.

I note that in terms of algorithmic complexity, it is no better than bubble sort -- it is quadratic in the size of the list. A nice property though is that it is pretty fast if the list is already mostly sorted.

-
If we modify bubble sort, we may not need to remember whether we made a swap in the memory, we can remember that in the turing state by adding a subroutine. – Shreesh Mar 29 at 7:08
Does gnome sort provably use the minimal number of moves? (i.e. not just minimal complexity, which "obviously" it does, but minimal number). Since the questioner doesn't specify, I suppose that minimum-on-average over all possible inputs is probably OK, but as you suggest by mentioning already-sorted data, minimum for every input would be ideal. – Steve Jessop Mar 29 at 9:06
@SteveJessop I'd doubt there exist an algorithm which does the minimum number of moves for every possible input. At least this is surely false in the more general context of sorting algorithms. – Bakuriu Mar 29 at 18:22

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.

-

The number of swaps of adjacent elements needed to order an array is equal to the number of inversions in the array. With n elements in total, there are at most n*(n-1)/2 inversions, so bubble sort gives the asymptotically optimal number of swaps in this model.

-
Actually, bubble sort will give exactly the optimal number of swaps. However, for each permutation there are several ways to do the optimal number of swaps, and it is not obvious which one reduces the total number of moves. (By bubble sort I mean "pick the largest non-sorted and move it to the end of sorted") – Peter Kravchuk Mar 28 at 22:02

The only algorithm with the two operators that you have mentioned which is quite efficient is the bubble sort. The complexity of the algorithm is $O(n^2)$ in the worst case.

I also assume apart from the two operations, we can also check whether we are at the rightmost (Op 3) or leftmost position (Op 4), either by use of sentinels $-\infty$ and $+\infty$ or by some operation on the list. Also we should have a comparison operation (Op 5) given separately or combined with swap operation. If the comparison operation is combined with the swap operation then it must tell us whether the swap was performed or not.

The algorithm that does not uses a boolean flag to know whether we have swapped any element or not, is given below (the trick to keep the information in the state of the machine, rather than memory):

Start:
Do until we are not at the leftmost position (Op 4)
move left (Op 2b)

Check:
If we are at rightmost position (Op 3)
goto Finished:
If current value is larger than next value (Op 5)
goto Unfinished:
move right (Op 2a)
Repeat Check:

Unfinished:
If we are at rightmost position (Op 3)
goto Start:
If current value is larger than next value (Op 5)
swap the elements (Op 1) and move right (Op 2a)
Repeat Unfinished:

Finished:
The list is sorted now, output it.


The solution of Eric Lippert, the gnome sort also works, because basically it is a two way bubble sort.

-
What about insertion sort? – Darkhogg Mar 28 at 12:42
Bubble sort needs at least two loop counters which are already more than allowed. – Raphael Mar 28 at 13:12
No, you can go left and right, and then right to left, until there is no change (which is maximum n times) without using counter. You don't even need extra space for a boolean flag to note if there is a change. If there is a change you just jump to another subroutine which does the same, except that it is another subroutine. – Shreesh Mar 28 at 13:51
And of course, I assume you can read blank at both the ends so you may know that it is beginning or end of list. Also, I assume we read both the current and next element to know whether we need to swap. – Shreesh Mar 28 at 13:58
Or, if we modify the operator swap as "swap if not in ascending order". – Shreesh Mar 28 at 14:36