And now, even more perl sixy...

natural_sort can be rewritten to do no copying and use no intermediate variables. It's kind of obfu but a lot more memory efficient. The » is the hyper operator. It is sort of like map. It means apply that method to each element in the supplied list.

sub natural_sort {
    return @_ if @_ < 2;
    my $index = 0;
    return @_[@_».lc».subst(/(\d+)/, -> $/{ sprintf( "%s%c%s", 0, $0.c
+hars, $0) }, :g).map( *~' '~$index++ ).sort.map({@(split(' ',$^_))[*-
+1]})];
}
[download]

natural_cmp can also use the hyper operator and is now using leg instead of cmp. leg is the string specific comparison operator. (l)ess-(e)qual-(g)reater

sub natural_cmp ($a, $b) {
   return [leg] ($a, $b)».lc».subst(/(\d+)/, -> $/{ sprintf( "%s%c%s",
+ 0, $0.chars, $0) }, :g);
}
[download]

A cached version could look something like below. Note: the cached version actually runs slower than the uncached version right now because of a bug in Rakudo * 2010.07. It evaluates both sides of the //= even if the lhs is defined. :-/ That should be fixed in the near future though. :-)

my %cache;
sub cached_natural_cmp ($a, $b) {
    return [leg] ($a, $b)».lc.map( %cache{ * } //= *.subst(/(\d+)/, ->
+ $/{ sprintf( "%s%c%s", 0, $0.chars, $0) }, :g));
}
[download]

Update: Actually, since perl6 has schwartzian transform semantics built into .sort, this could be very concisely rewritten as:

 @array.sort(*.lc.subst(/(\d+)/, -> $/{ sprintf( "%s%c%s", 0, $0.chars
+, $0) }, :g));
[download]

or, my favorite:

@array.sort: natural(*);
   
sub natural ($) { *.lc.subst(/(\d+)/, -> $/{ sprintf( "%s%c%s", 0, $0.
+chars, $0) }, :g) }
[download]

used as

.say for %words.keys.sort: natural(*);

or 

%words.keys.sort( natural(*) )».say;
[download]

That's just beautiful.