# mergesort

sub merge
{
    my ($l,$r) = @_;
    my @L = @$l;
    my @R = @$r;
    my ($i, $j) = (0,0);
    my @A = (); # list to be built
    while ($i<@L || $j<@R)
    {
	if ($i<@L && ($j>=@R || $L[$i]<$R[$j])) {push(@A,$L[$i++]);}
	else {push(@A,$R[$j++]);}
    }
    @A;
}

sub mergesort
{
    my @A = @_;
    if (@A<2) { return @A; }
    my $mid = $#A/2;
    my @L = @A[0..$mid];
    my @R = @A[$mid+1..$#A];
    @L = mergesort(@L);
    @R = mergesort(@R);
    merge(\@L, \@R);
}

@m = (3,8,1,5,2,6,9,4,0,7);
print mergesort(@m);
