基数ソート

use strict;
use warnings;
use Data::Dumper;
my $trials = 40;
my %h = map { int rand $trials => 1 } 1..$trials;
my @target = keys %h;

print join("  ", @target);
print "\n";

@target = radix_sort(@target);

sub radix_sort {
  my @tupples = map { [$_, $_] } @_;
  my $flag = 1;
  while ($flag) {
    my @buckets;
    $flag = 0;
    for my $tupple (@tupples) {
      my ($copy, $original) = @$tupple;
      my $key = 1 & $copy;
      $flag |= $key;
      $buckets[$key] ||= [];
      push @{ $buckets[$key] }, [$copy >> 1, $original];
    }
    @tupples = map { @{$_} } grep { defined } @buckets;
    print join("  ", map { $_->[1] } @tupples);
    print "\n";
  }
  map { $_->[1] } @tupples;
}

33  32  21  26  2  1  18  0  23  16  13  27  25  6  39  36  3  12  15  20  8  38  34  10  31  5
32  26  2  18  0  16  6  36  12  20  8  38  34  10  33  21  1  23  13  27  25  39  3  15  31  5
32  0  16  36  12  20  8  33  21  1  13  25  5  26  2  18  6  38  34  10  23  27  39  3  15  31
32  0  16  8  33  1  25  26  2  18  34  10  27  3  36  12  20  21  13  5  6  38  23  39  15  31
32  0  16  33  1  2  18  34  3  36  20  21  5  6  38  23  39  8  25  26  10  27  12  13  15  31
32  0  33  1  2  34  3  36  5  6  38  39  8  10  12  13  15  16  18  20  21  23  25  26  27  31
0  1  2  3  5  6  8  10  12  13  15  16  18  20  21  23  25  26  27  31  32  33  34  36  38  39
0  1  2  3  5  6  8  10  12  13  15  16  18  20  21  23  25  26  27  31  32  33  34  36  38  39

1回目、2回目、3回目のソートでそれぞれ2,4,8で割った余りごとにソートされていき最後にちゃんとソートされる。これは面白い。