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.

In reply to Re: Algorithm Pop Quiz: Sorting by clintp
in thread Algorithm Pop Quiz: Sorting by clintp

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.