挿入ソート

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

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

@target = isort(@target);


sub isort {
  my @ary = @_;
  my @ret = (shift @ary);
  while (1) {
    my $element = shift @ary;
    defined $element or last;
    my @temp;
    while (1) {
      my $shift = shift @ret;
      unless (defined $shift) {
        @temp = (@temp, $element);
        last;
      }
      if ($shift < $element) {
        @temp = (@temp, $shift);
      }
      else {
        @temp = (@temp, $element, $shift, @ret);
        last;
      }
    }
    @ret = @temp;
    print join("  ", @ret);
    print "\n";
  }
  @ret;
}

6  11  3  9  12  8  1  4  0  10
6  11
3  6  11
3  6  9  11
3  6  9  11  12
3  6  8  9  11  12
1  3  6  8  9  11  12
1  3  4  6  8  9  11  12
0  1  3  4  6  8  9  11  12
0  1  3  4  6  8  9  10  11  12