Here's a basic quicksort implementation. Because we don't have random access to the stack, I've used the top element as the pivot. That has the unfortunate effect that we get worst-case (quadratic) behaviour if the input list is already sorted! Bubblesort would actually be better in that case. For a random input list, the asymptotic behaviour should be O(n log n), on the assumption that rotate_up takes constant time.

I think it'll translate to fewer than 50 instructions of assembler, but I don't have kids or a car :-)

sub debug ($;@) {
    # Uncomment the next line to see a partial execution trace
    # print @_;
}

my @stack = @ARGV;              # Initialise the stack with test value
+s
push @stack, scalar(@stack);    # Push the length

quicksort();                    # call the sort routine
print "Result: @stack\n";       # and print the result


sub quicksort {
    local ($n) = pop(@stack);
    push @stack, $n;
    push @stack, 0;
    sort_and_tuck();
    push @stack, $n;
}

sub sort_and_tuck {
    local ($w) = pop(@stack);           # where to put result
    local ($c) = pop(@stack);           # number of items
    debug "    \$w=$w; \$c=$c; \@stack=@stack\n";
    
    if    ($c == 1) {
        rotate_up($w+1);
    }
    elsif ($c > 1) {
        local ($p) = pop(@stack);       # pivot
        $c--;
        local ($n) = $c;
        local ($i) = $c;
        debug "\t< \$p=$p; \$n=$n";

        while ($i--) {
            local ($e) = pop(@stack);   # examine top element
            push @stack, $e;
            debug "\t\t\$e=$e (@stack)\n";
            if ($p gt $e) {
                rotate_up($c);
                -- $n;
            }
            else {
                rotate_up($n);
            }
        }
        
        debug "\t> \$n=$n\n";

        # Now we've partitioned the list. The top $n elements are gt $
+p,
        # and the next ($c-$n) are le $p. Sort the partitions.
        local($r) = $c-$n;

        push @stack, $n;
        push @stack, $w+$r;
        sort_and_tuck();
        
        push @stack, $r;
        push @stack, $w;
        sort_and_tuck();

        push @stack, $p;                # Reinsert the pivot
        rotate_up(1+$w+$r);

        debug "    Return: @stack\n"
    }
}



# Should be called put_away(), but I'm not allowed to modify it ;-)
sub rotate_up {
        local($a,$b);
        $a=$_[0];
        $a--;
        return if $a<1;
        $b=pop @stack;
        splice(@stack, -$a, 0, $b);
}
[download]