#!/usr/bin/perl

###########################################################
#   Mergesort 
# Code from O'Reilly Algorithms book
# Testing performed by Glein
#
#
#
#
#
#
###########################################################

use warnings;
use strict;

use Benchmark;

#srand(1);   # not needed

my @dictionary = reverse 'aa'..'bb';
# print "@dictionary";

my @work;

for (@dictionary){
  if (rand() < 0.5) {
    $_ = ucfirst;
  }
  if (rand() < 0.25) {
    substr($_, rand(length), 0) = '_';
  }
  if (rand() < 0.333) {
    $_ .= $_;
  }
  if (rand() < 0.333) {
    $_ .=  reverse $_;
  }
  if (rand() > 1/length) {
    substr($_, rand(length), rand(length)) = '';
  }
  print $_ . "\n";
}

print "That was unsorted. This IS sorted: \n";

mergesort( \@dictionary );

for (@dictionary){
  print $_ . "\n";
}

print " work : @work \n ";

sub mergesort {
  my ($array) = @_;

  my @array_test = @$array;
  print " array before sort : @array_test \n";

  mergesort_recurse ( $array,  0,  $#{$array}   );

}

sub mergesort_recurse {
  my ($array, $first, $last) = @_;
  
  if ($last < $first) {
    local $^W = 0;
    my $middle = int(( $last + $first)/2);

    mergesort_recurse($array, $first, $middle);
    mergesort_recurse($array, $middle + 1, $last);
    merge($array, $first, $middle, $last);
  }
}


sub merge {
  my ( $array, $first, $middle, $last ) = @_;

  my $n = $last - $first +1;

  for (my $i = $first, my $j = 0; $i <= $last; ){
    $work[$j++] = $array->[$i++];
  }

  $middle = int(($first + $last) / 2) if $middle > $last;

  my $n1 = $middle - $first + 1;

  for ( my $i = $first, my $j = 0, my $k = $n1; $i <= $last; $i++) {
    $array->[$i] = 
      $j < $n1 && 
	($k == $n || $work[$j] lt $work[$k]) ?
	  $work[$j++] :
	    $work[$k++];
  }
}


