Shell sort

sort-shell.pl

#!/usr/bin/perl

use warnings;
use strict;
use feature 'say';

my @array = (5, 3, 7, 9, 2, 1, 6, 5, 3, 7, 9, 3, 4);

say "@array - initial";

for (my $k = int @array / 2; $k > 0; $k = int $k / 2) {
    # Do a gapped insertion sort for this gap size.
    # The first gap elements a[0..gap-1] are already in gapped order
    # keep adding one more element until the entire array is gap sorted
    for (my $i = $k; $i < @array; ++$i) {
        # add a[i] to the elements that have been gap sorted
        # save a[i] in temp and make a hole at position i
        my $temp = $array[$i];
        # shift earlier gap-sorted elements up until the correct location for a[i] is found
        my $j;
        for ($j = $i; $j >= $k && $array[$j - $k] > $temp; $j -= $k) {
            $array[$j] = $array[$j - $k];
        }
        # put temp (the original a[i]) in its correct location
        $array[$j] = $temp;
    }
    say "@array";
}

#5 3 7 9 2 1 6 5 3 7 9 3 4 - initial
#4 3 3 7 2 1 5 5 7 9 9 3 6
#4 2 1 5 3 3 6 5 3 7 9 7 9
#1 2 3 3 3 4 5 5 6 7 7 9 9