#!/usr/bin/perl
 
use Data::Dumper;
use POSIX qw(ceil floor);
use strict;
 
my @a = (12, 7, 8, 15, 1, 11, 2, 5);
#@a = reverse(@a);
 
our $ident = "";
 
sub mergesort
{
  my ($a, $l, $r) = @_;
  if ($l < $r)
  {
    my $m = floor(($l+$r)/2);
    #print $ident, "mergesort(a, $l, $r) (m=$m)", $/;
    #$ident .= "  ";
    mergesort($a, $l, $m);
    mergesort($a, $m+1, $r);
    print $ident, "--------> a=", print_array($a), $/;
    merge($a, $l, $m, $r);
    print $ident, "--------> a=", print_array($a), $/;
    #$ident = substr($ident, 0, length($ident)-2);
  }
}
 
sub merge
{
  my ($a, $l, $m, $r) = @_;
  #print $ident, "l=$l, m=$m, r=$r", $/;
 
  my $i = $l;
  my $j = $m + 1;
  my $k = $l;
  my @b = ();
  #print $ident, "a=", print_array($a), $/;
  while($i <= $m && $j <= $r)
  {
    #print $ident, "i=$i, j=$j, k=", $k, "  $a[$i] <= $a[$j]", $/;
    if ($$a[$i] >= $$a[$j])
    {
      $b[$k] = $$a[$i];
      $i++;
    }
    else
    {
      $b[$k] = $$a[$j];
      $j++;
    }
    $k++;
    #print $ident, "b=", print_array(\@b), $/;
  }
 
  if ($i > $m)
  {
    for (my $h = $j; $h <= $r; $h++)
    {
      #print $ident, "x=", $k+$h-$j, $/;
      $b[$k + $h - $j] = $$a[$h];
    }
  }
  else
  {
    for (my $h = $i; $h <= $m; $h++)
    {
      #print $ident, "y=", $k+$h-$i, $/;
      $b[$k + $h - $i] = $$a[$h];
    }
  }
  #print $ident, "b=", print_array(\@b), $/;
 
  for(my $h = $l; $h <= $r; $h++)
  {
    $$a[$h] = $b[$h];
  }
  #print $ident, "a=", print_array($a), $/;
}
 
my $a = \@a;
print $ident, "in=", print_array($a), $/;
mergesort($a, 0, scalar(@$a) - 1);
print $ident, "out=", print_array($a), $/;
 
sub print_array
{
  my ($a) = @_;
  my $str = "[";
  for(my $i = 0; $i < scalar(@$a); $i++)
  {
    $str .= ((defined($$a[$i])) ? $$a[$i] : "_");
    $str .= ", ";
  }
  $str = substr($str, 0, length($str)-2);
  $str .= "]";
  return $str;
}