> When using a signed integer variable to represent an index, there is an entire range of negative numbers that are not useful at all. Let's make use of them, then.

If you have "local variable" with more bits than log(# elements to be sorted), then yes, this trick works, but with sufficient extra bits, you can pack multiple indexes into a single variable by shifting and 'or'ing.

An even sneakier way of hiding this extra bit is to use the program counter to store it:

  a:
    int i = 0
    FOR (; i < # elems-1; ++i)
         IF pair(i, i+1) is out of order
             swap pair; goto b
    RETURN
  b:
    FOR (; i < # elems-1; ++i)
         IF pair(i, i+1) is out of order
             swap pair
    GOTO a

If the program is running the "b" loop, some pair has been swapped, so when it finishes the loop, it knows to re-run the "a" loop. If the program completes the "a" loop, it knows no pair was swapped, and can finish.

Edit: formatting