$ cat qsort.pl
#!/usr/bin/env perl
#
#   example of recursion using quicksort
#
use strict;
use warnings;

# quicksort -- recursively sort a list by taking the first
# element and using that as the "center" value, and breaking
# the rest of the list into two lists: those lower than the
# center value and those higher than the center value.
#
# then return qsort(lower), center, qsort(higher)
#
# The degenerate case is when you have a single value in your
# list -- simply return it.
#
# This version helps illustrate the recursion by describing
# what it's doing, with indentation to show the nesting of the
# calls.
#
sub list_sort {
    my ($lev, @vals) = @_;

    #print "  "x$lev, "qs(", join(" ", @vals), ")\n";
    print "  "x$lev, "qs(@vals)\n";
    ++$lev;

    if (@vals < 2) {
        print "  "x$lev, "degenerate case, returning (@vals)\n";
        return @vals;
    }

    my $split_val = shift @vals;
    my @lower  = grep { $_ lt $split_val } @vals;
    my @higher = grep { $_ gt $split_val } @vals;
    print "  "x$lev, "(@lower), $split_val, (@higher)\n";

    @vals = (
        list_sort($lev, @lower),
        $split_val,
        list_sort($lev, @higher)
    );
    print "  "x$lev, "returning (@vals)\n";
    return @vals;
}

my @list = qw(c a h f g e b d i);
print "ORIG: @list\n";

@list = list_sort(0, @list);

print "DONE: @list\n";

$ perl qsort.pl
ORIG: c a h f g e b d i
qs(c a h f g e b d i)
  (a b), c, (h f g e d i)
  qs(a b)
    (), a, (b)
    qs()
      degenerate case, returning ()
    qs(b)
      degenerate case, returning (b)
    returning (a b)
  qs(h f g e d i)
    (f g e d), h, (i)
    qs(f g e d)
      (e d), f, (g)
      qs(e d)
        (d), e, ()
        qs(d)
          degenerate case, returning (d)
        qs()
          degenerate case, returning ()
        returning (d e)
      qs(g)
        degenerate case, returning (g)
      returning (d e f g)
    qs(i)
      degenerate case, returning (i)
    returning (d e f g h i)
  returning (a b c d e f g h i)
DONE: a b c d e f g h i