#!perl
use strict;
my ($list_size, $max_num, @numbers, $start_time);
#Generate a large number of random integers
$list_size = 100000;
$max_num = 1000;
@numbers = ();
for(1..$list_size) {
push(@numbers, int(rand($max_num)));
}
#Print out the number array, then sort it, then print it out again in sorted order
#print "\n\n@numbers";
$start_time = time;
@numbers = @{mergesort(\@numbers)};
#print "\n\n@numbers";
print "MERGESORT sorted $list_size random integers between 1 and $max_num in " . (time - $start_time) . " seconds\n";
#Mergesort works by dividing the list into two halves and recursing on each half.
#Lists of zero or one element are considered sorted by definition
#At the tail end of recursion, we merge the lists in the correct order
sub mergesort {
my ($numbers, @numbers, $nums_size, @L, @R);
($numbers) = @_;
@numbers = @{$numbers};
$nums_size = $#numbers + 1;
if( $nums_size > 1 ) {
@L = @numbers[0..($nums_size/2)-1];
@R = @numbers[($nums_size/2)..$nums_size-1];
$numbers = merge(mergesort(\@L), mergesort(\@R));
}
return $numbers;
}
sub merge {
my (@merged, @left, @right, $L, $R);
@left = @{$_[0]};
@right = @{$_[1]};
@merged = ();
for($L = shift @left, $R = shift @right; defined $L or defined $R; ) {
if( ! defined $R ) {
push @merged, $L;
$L = shift @left;
}
elsif( ! defined $L ) {
push @merged, $R;
$R = shift @right;
}
elsif( $L <= $R) {
push @merged, $L;
$L = shift @left;
}
else {
push @merged, $R;
$R = shift @right;
}
}
return \@merged;
}
I don't have a lot to say, but this is my little bit.
Saturday, September 12, 2009
Mergesort in perl
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment