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);
}
}