Download | Plain Text | No Line Numbers 

  1. #!/usr/bin/perl
  2.  
  3. use Data::Dumper;
  4. use POSIX qw(ceil floor);
  5. use strict;
  6.  
  7. my @a = (12, 7, 8, 15, 1, 11, 2, 5);
  8. #@a = reverse(@a);
  9.  
  10. our $ident = "";
  11.  
  12. sub mergesort
  13. {
  14.   my ($a, $l, $r) = @_;
  15.   if ($l < $r)
  16.   {
  17.     my $m = floor(($l+$r)/2);
  18.     #print $ident, "mergesort(a, $l, $r) (m=$m)", $/;
  19.     #$ident .= "  ";
  20.     mergesort($a, $l, $m);
  21.     mergesort($a, $m+1, $r);
  22.     print $ident, "--------> a=", print_array($a), $/;
  23.     merge($a, $l, $m, $r);
  24.     print $ident, "--------> a=", print_array($a), $/;
  25.     #$ident = substr($ident, 0, length($ident)-2);
  26.   }
  27. }
  28.  
  29. sub merge
  30. {
  31.   my ($a, $l, $m, $r) = @_;
  32.   #print $ident, "l=$l, m=$m, r=$r", $/;
  33.  
  34.   my $i = $l;
  35.   my $j = $m + 1;
  36.   my $k = $l;
  37.   my @b = ();
  38.   #print $ident, "a=", print_array($a), $/;
  39.   while($i <= $m && $j <= $r)
  40.   {
  41.     #print $ident, "i=$i, j=$j, k=", $k, "  $a[$i] <= $a[$j]", $/;
  42.     if ($$a[$i] >= $$a[$j])
  43.     {
  44.       $b[$k] = $$a[$i];
  45.       $i++;
  46.     }
  47.     else
  48.     {
  49.       $b[$k] = $$a[$j];
  50.       $j++;
  51.     }
  52.     $k++;
  53.     #print $ident, "b=", print_array(\@b), $/;
  54.   }
  55.  
  56.   if ($i > $m)
  57.   {
  58.     for (my $h = $j; $h <= $r; $h++)
  59.     {
  60.       #print $ident, "x=", $k+$h-$j, $/;
  61.       $b[$k + $h - $j] = $$a[$h];
  62.     }
  63.   }
  64.   else
  65.   {
  66.     for (my $h = $i; $h <= $m; $h++)
  67.     {
  68.       #print $ident, "y=", $k+$h-$i, $/;
  69.       $b[$k + $h - $i] = $$a[$h];
  70.     }
  71.   }
  72.   #print $ident, "b=", print_array(\@b), $/;
  73.  
  74.   for(my $h = $l; $h <= $r; $h++)
  75.   {
  76.     $$a[$h] = $b[$h];
  77.   }
  78.   #print $ident, "a=", print_array($a), $/;
  79. }
  80.  
  81. my $a = \@a;
  82. print $ident, "in=", print_array($a), $/;
  83. mergesort($a, 0, scalar(@$a) - 1);
  84. print $ident, "out=", print_array($a), $/;
  85.  
  86. sub print_array
  87. {
  88.   my ($a) = @_;
  89.   my $str = "[";
  90.   for(my $i = 0; $i < scalar(@$a); $i++)
  91.   {
  92.     $str .= ((defined($$a[$i])) ? $$a[$i] : "_");
  93.     $str .= ", ";
  94.   }
  95.   $str = substr($str, 0, length($str)-2);
  96.   $str .= "]";
  97.   return $str;
  98. }
  99.