&gt; 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&#x27;s make use of them, then.<p>If you have &quot;local variable&quot; 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 &#x27;or&#x27;ing.<p>An even sneakier way of hiding this extra bit is to use the program counter to store it:<p><pre><code>  a:
    int i = 0
    FOR (; i &lt; # elems-1; ++i)
         IF pair(i, i+1) is out of order
             swap pair; goto b
    RETURN
  b:
    FOR (; i &lt; # elems-1; ++i)
         IF pair(i, i+1) is out of order
             swap pair
    GOTO a
</code></pre>
If the program is running the &quot;b&quot; loop, some pair has been swapped, so when it finishes the loop, it knows to re-run the &quot;a&quot; loop.  If the program completes the &quot;a&quot; loop, it knows no pair was swapped, and can finish.<p>Edit: formatting