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]

In reply to Quicksort (of a stack) by robin
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.