[thelema314]

> 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

[userbinator]

That's the essence of a goto-based state machine (one of the few problems where gotos are the most natural solution), compared to the alternative of storing the state in a variable and doing an extra indirection every transition to "go to" the right one.

[kpil]

I guess you can move an arbitrary amount of booleans (or enums) into the running state.

I suppose that the very idea of variables is just to separate the state from the code so that it's possible to handle complex states in generic code with a reasonable size...

On the other hand, a lot of bugs are related to that the resulting implicit state machine is not complete and/or correct...

The same question but including the program state is the interresting one. How much information/state is needed and needs to be shared, as it relates to how an algorithm scales.