Perlでマージソート

use strict;
use warnings;

my @sample;
for(my $i=0; $i<100; $i++){
    push @sample, int(rand 100);
}

merge_sort(\@sample, 0, @sample-1);

foreach my $item (@sample){
    print "$item\n";
}


sub merge{
    my ($A, $p, $q, $r) = @_;

    my $n1 = $q-$p+1;
    my $n2 = $r-$q;

    my @L;
    my @R;

    for(my $i=0; $i<$n1; $i++){
        $L[$i] = $A->[$p+$i];
    }

    for(my $i=0; $i<$n2; $i++){
        $R[$i] = $A->[$q+1+$i];
    }

    $L[$n1] = 'inf'+0;
    $R[$n2] = 'inf'+0;

    my $i = 0;
    my $j = 0;
    for(my $k=$p; $k<=$r; $k++){
        if($L[$i] <= $R[$j]){
            $A->[$k] = $L[$i];
            $i++;
        }else{
            $A->[$k] = $R[$j];
            $j++;
        }
    }
}

sub merge_sort{
    my ($A, $p, $r) = @_;
    if($p < $r){
        my $q = int(($p+$r)/2);
        merge_sort($A, $p, $q);
        merge_sort($A, $q+1, $r);
        merge($A, $p, $q, $r);
    }
}