Perlでクイックソート

wikipediaのCのサンプルをPerlに起こした感じのやつ。
無駄に再帰回数が多い気がしなくもない。
どっか間違ったかも。

#!/usr/bin/env perl
use strict;
use warnings;

my @a = (3, 2, 0, 5, 8, 3, 4, 1, 3, 2);
my @b = @a;
qs(\@b, 0, $#b);

print @a, "\n";
print @b, "\n";

sub qs {
    my ($a, $left, $right) = @_;
    my ($i, $j) = ($left, $right);
    my $pivot = $a->[$i];
    while(1){
        while($a->[$i] < $pivot){ $i++ }
        while($a->[$j] > $pivot){ $j-- }
        last if $i >= $j;
        ($a->[$i], $a->[$j]) = ($a->[$j], $a->[$i]);
        $i++; $j--;
    }
    return if $left >= $right;
    qs($a, $left, $i - 1);
    qs($a, $j + 1, $right);
}

配列リファレンス渡しじゃなくて、結果の配列を連結してみた。
再帰は少ないけど上のより遅い。 あとメモリも食いそう。

#!/usr/bin/env perl
use strict;
use warnings;

my @a = (3, 2, 0, 5, 8, 3, 4, 1, 3, 2);
my @b = @a;

@b  = qs(@b);

sub qs {
    my $t = $_[0];
    my (@same, @high, @low);
    for(@_){
        push @same, $_ if $_ == $t;
        push @high, $_ if $_ > $t;
        push @low, $_ if $_ < $t;
    }
    @high = qs(@high) if @high > 1;
    @low = qs(@low) if @low > 1;
    return map { $_ if defined } @low, @same, @high;
}