What is the most efficient constant-space sorting algorithm?

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.

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

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.