Okay, here's my solution and it's -- horror of horrors -- a classic bubble sort. Since I had already implemented PEEK and REPLACE (for other things I needed) writing a simple bubble sort wasn't too much of a bother.

Everyone seemed to do the same sort of modified bubble sort, but they're more efficient than mine being self-contained and not requiring SWAP and PEEK. With no objections I'd like to borrow the general algorithm for an OSS project -- this PerlMonks thread cited.

Unless something frighteningly better comes along.

# Stack Library
#  This'll get a whole lot cleaner when I can tell the
#  depth of the stack automagically

# peek -- return whatever string is on the stack
#   Inputs: the offset on the stack
#  Outputs: the string
# Non-Destructive!
# Does *not* test for bounds conditions
PEEK:   pushi
    restore I0
    set I3, I0
    inc I0
    set I2 0
PLOOP:  ge I2, I3, POL
    rotate_up I0
    inc I2
    branch PLOOP
POL:
    restore S0
    save S0
    eq I0, 0, EOP
    rotate_up I0

EOP:    save S0
    popi
    ret

# REPLACE -- replace thing at stack position X
#   Inputs: the offset to remove
#        the string to leave in its place
#  Outputs: The string removed
#     Note: Almost *identical* to PEEK above
# Does *not* test for bounds conditions
REPLACE: pushi
    pushs
    restore S1
    restore I0
    set I3, I0
    inc I0
    set I2, 0
RLOOP:    ge I2, I3, ROL
    rotate_up I0
    inc I2
    branch RLOOP
ROL:    restore S0
    save S1
    eq I0, 0, ENDOFREPLACE
    rotate_up I0
ENDOFREPLACE:
    save S0
    popi
    pops
    ret

# swap -- swap the position of two strings on the stack
#  Inputs: Offsets of the two things on the stack
# Outputs: None.
# Does *not* test for bounds conditions
SWAP:    pushi
    pushs

    restore I0
    restore I1
    save I0
    save "-"     # Just a dummy
    bsr REPLACE

    restore S0
    save I1
    save S0

    bsr REPLACE

    restore S1
    save I0
    save S1

    bsr REPLACE
    restore S1   # dummy
        popi
    pops
    ret

# Sort whatever's on the stack.
#   Yes, this is a bubble sort.  Get over it.
#  Inputs:  Stack depth on top of the stack
# Outputs:  Stack depth on top of the stack
SORTSTACK:
    pushi
    pushs
    restore I5
    set I0, 0
    set I1, 0
BUBBLE: inc I1
    le I1, I0, BUB1
    set I1, 0
    inc I0
BUB1:    ge I0, I5, SORTEND
    save I1
    bsr PEEK
    restore S2
    save I0
    bsr PEEK
    restore S3
    le S2, S3, BUBBLE
    save I1
    save I0
    bsr SWAP
    branch BUBBLE

SORTEND:
    save I5
    popi
    pops
    ret
[download]

What? You expected me to post Perl code? :)

Now, can you write me a general purpose expression evaluator given just the tokens on the stack? and...oh nevermind.