Sorting in the stack

Five batteries, five charge levels. Which one is the second weakest? Minimum only tells you the weakest. Whoever needs a ranking has to sort – and IC10 has no instruction for it. You build it yourself.

Ordering values: bubble sort#

The simplest method always compares two neighbours and swaps them if they are the wrong way round. After one pass the largest value is right at the back. The next pass does not need to touch it any more and is one step shorter.

Swapping with registers#

IC10 has no swap. You swap two stack slots through two registers: read both, write back crosswise.

get a db j
add k j 1
get b db k
ble a b next        # already in order
poke j b
poke k a
next:

The jump over the swap means: if the two are already in the right order, everything stays as it is. Equal values are not swapped either, hence ble and not blt.

Two loops#

The inner loop runs over the pairs with j, the outer one shortens the limit after every pass:

sub limit COUNT 1
outer:
move j 0
inner:
add j j 1
blt j limit inner
sub limit limit 1
bgtz limit outer

Cost per tick#

For n values bubble sort compares n · (n − 1) / 2 pairs. Each comparison costs about eight instructions here:

The chip pauses after 128 instructions by itself and carries on in the next tick. With 50 values sorting therefore takes almost 40 seconds – and during that time the chip does nothing else.