"血をもって書け。そうすればあなたは、血が精神だということを経験するだろう。"

シェルソート

挿入ソートを流用。少し手がかかった。。。

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

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

@target = shell_sort(@target);

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

sub shell_sort {
  my @ary = @_;
  my $max_index = $#ary;
  my $interval = $max_index >> 1;
  while ($interval) {
    my $key = 0;
    my @h = ( [] ) x $interval;
    while (1) {
      my $shift = shift @ary;
      defined $shift or last;
      $h[$key] = [@{ $h[$key] }, $shift];
      $key++;
      $key %= $interval;
    }
    $h[$_] = [isort(@{ $h[$_] })] for 0..$interval-1;
    push @ary, (shift @{ $h[$_ % $interval] }) for 0..$max_index;
    print join("  ", map { ( $_ %  $interval ? '  ' : '| ') . $ary[$_] } 0..$max_index);
    print " (interval : $interval) \n";
    $interval >>= 1;
  }
  @ary;
}

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;
  }
  @ret;
}

部分的に挿入ソート(別に何ソートでもいいような気もするけど)していく。たとえば2段目では(0,10,20,21,28),(2,3,5,8,13)という部分列がそれぞれソートされている。

21  2  1  18  0  13  27  6  28  3  9  12  20  8  24  19  10  5
| 10    2    1    12    0    8    24    6  | 21    3    9    18    20    13    27    19  | 28    5 (interval : 8) 
| 0    2    1    6  | 10    3    9    12  | 20    5    24    18  | 21    8    27    19  | 28    13 (interval : 4) 
| 0    2  | 1    3  | 9    5  | 10    6  | 20    8  | 21    12  | 24    13  | 27    18  | 28    19 (interval : 2) 
| 0  | 1  | 2  | 3  | 5  | 6  | 8  | 9  | 10  | 12  | 13  | 18  | 19  | 20  | 21  | 24  | 27  | 28 (interval : 1) 
0  1  2  3  5  6  8  9  10  12  13  18  19  20  21  24  27  28