Algorithm Pop Quiz: Sorting

[clintp]

This isn't a problem to test your Perl smarts. It's one to test your programming smarts. :)

Working on a side-project indirectly involved with Parrot, I recently came across a tough problem. I managed to solve it, but the solution is inelegant. Here's the problem:

Given these resources:

• A single stack, with the depth of the stack stored on top and strings to be sorted below that.
• The depth of the stack is arbitrary.
• Your tools for manipulating and examining the stack are exclusively limited to: push, pop, and rotate_up() (see below)
• No other stacks (arrays, hashes, etc..) or data structures allowed.
• But as many scalar variables as you wish
• You can use branches, conditional logic, loops, comparison operators, even functions (see next item), and any other control logic you wish.
• No lexical variables or closures are permitted. local() would be allowed.
• Running off the end of the stack (on either side) is a fatal exception.
• The stack *must* be returned in its original state. You may not manipulate items *below* the given depth.

Design a routine to sort the stack, and return to the caller with the stack looking like it did before (depth on top) except sorted below that point.

The restrictions, of course, are based on the current Parrot opcode set. Imagine yourself programming in assembly language...

A sample stack might be:

@stack=qw(d b f a e c 6);  # <-- bottom .. top -->

and you would have to produce:

@stack=qw(f e d c b a 6);  # <-- bottom .. top -->

The rotate_up instruction takes the thing on top of the stack and shifts it farther down in the stack, moving all of the displaced elements up a notch. rotate_up(0) and rotate_up(1) are no-ops. rotate_up with a negative number will throw a fatal exception.

# You are not allowed to modify this.
sub rotate_up {
        local($a,$b);
        $a=$_[0];
        $a--;
        return if $a<1;
        $b=pop @stack;
        splice(@stack, -$a, 0, $b);
}

So can ya do it?

Points are given for:

1. Elegance. Did it take you 300 instructions to do it? Too bad. Mine worked in about 100 and it's for crap. :)
2. Simplicity. The flipside of elegance. The ease of which this translates to machine code will swell your karma.
3. Speed. Pull off a bubblesort in 50 instructions, and I'll be impressed. Do a quicksort in 50 and I'll babysit your kids and wash your car.

Points are deducted for:

1. Golfing in an obfuscatory manner. When I go to translate your solution back into PASM, I'll be very, very upset with golfers and obfu "artists".
2. Violating the spirit of things. Being cute with eval to modify the stack? Simulating arrays with namespace manipulation? Poser.

If you need inspiration or think this is beneath you: I'd like you to consider the Story of Mel and what a Real Hacker would do. :)

I'll post my solution as a reply on Monday March 25th at 5pm Eastern Standard time. You may be horrified. :)