#!/usr/bin/perl

sub mergesort_iter ($) {
    my ( $array ) = @_;

    my $N    = @$array;
    my $Nt2  = $N * 2; # N times 2.
    my $Nm1  = $N - 1; # N minus 1.

    $#work = $Nm1;

    for ( my $size = 2; $size < $Nt2; $size *= 2 ) {
        for ( my $first = 0; $first < $N; $first += $size ) {
            my $last = $first + $size - 1;
            merge( $array,
                   $first,
                   int(($first + $last) / 2),
                   $last < $N ? $last : $Nm1 );
        }
    }
}

sub merge {
    my ( $array, $first, $middle, $last ) = @_;

    my $n = $last - $first + 1;

    # Initialize work with relevant elements from the array.
    for ( my $i = $first, my $j = 0; $i <= $last; ) {
        $work[ $j++ ] = $array->[ $i++ ];
    }

    # Now do the actual merge.  Proceed through the work array
    # and copy the elements in order back to the original array.
    # $i is the index for the merge result, $j is the index in
    # first half of the working copy, $k the index in the second half.

    $middle = int(($first + $last) / 2) if $middle > $last;

    my $n1 = $middle - $first + 1;    # The size of the 1st half.

    for ( my $i = $first, my $j = 0, my $k = $n1; $i <= $last; $i++ ) {
        $array->[ $i ] =
            $j < $n1 &&
              ( $k == $n || $work[ $j ] lt $work[ $k ] ) ?
                $work[ $j++ ] :
                $work[ $k++ ];
    }
}

@array = qw(Wait, wait, I thought of something to say!  It was more of a question, though.);

mergesort_iter( \@array );

print "@array\n";