#!/usr/bin/perl

sub insertion_sort {
    my $array = shift;

    my $i;      # The initial index for the minimum element.
    my $j;      # The running index for the minimum-finding scan.

    for ( $i = 0; $i < $#$array; $i++ ) {
        my $m = $i;             # The final index for the minimum element.
        my $x = $array->[ $m ]; # The minimum value.

        for ( $j = $i + 1; $j < @$array; $j++ ) {
            ( $m, $x ) = ( $j, $array->[ $j ] ) # Update minimum.
              if $array->[ $j ] lt $x;
        }

        # The double-splice simply moves the $m-th element to be
        # the $i-th element.  Note: splice is O(N), not O(1).
        # As far as the time complexity of the algorithm is concerned
        # it makes no difference whether we do the block movement
        # using the preceding loop or using splice().  Still, splice()
        # is faster than moving the block element by element.
        splice @$array, $i, 0, splice @$array, $m, 1 if $m > $i;
    }
}

@array = qw(for a good algorithm call abigail at 104-5876);

insertion_sort(\@array);

print "@array\n";