Download and view my resume (PDF)

Saturday, September 12, 2009

Mergesort in perl

This is mergesort implemented in perl. This implementation run on a Macbook Pro 2.4GHz Dual Core machine sorts 100,000 random integers between 1 and 1000 in about three seconds. It sorts 1,000,000 integers in 37 seconds, whereas my implementation of quicksort takes 165 seconds, which leads me to believe that there is something amiss with my quicksort.

#!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;
}

No comments:

Post a Comment