#!/usr/bin/perl

sub insertion_merge {
    my ( $large, $small ) = @_;

    my $merge;  # The merged result.
    my $i;      # The index to @merge.
    my $l;      # The index to @$large.
    my $s;      # The index to @$small.

    $#$merge = @$large + @$small - 1; # Pre-extend.

    for ( ($i, $l, $s) = (0, 0, 0); $i < @$merge; $i++ ) {
        $merge->[ $i ] =
          $l < @$large &&
            ( $s == @$small || $large->[ $l ] < $small->[ $s ] ) ?
              $large->[ $l++ ] :
              $small->[ $s++ ] ;
    }

    return $merge;
}

@large = qw( 1  4  9 16 25 36 49 64 81 100);
@small = qw( 2  5 11 17 23);
$merge = insertion_merge( \@large, \@small );
print "@{$merge}\n";