sub merge {
	my ($left, $right) = @_; 
	my @merged;

	while ((scalar(@$left) > 0) && (scalar(@$right))) {

		if ($left->[0] <= $right->[0]) {
			push @merged, shift(@$left);
		} else {
			push @merged, shift(@$right);
		}
	}

	if (scalar(@$left) > 0) {
		push @merged, shift(@$left);
	}
	
	if (scalar(@$right) > 0) {
		push @merged, shift(@$right);
	}

	return @merged;
}
		 

sub mergesort {
	my @list = @_;
	my (@left,@right);


	if (scalar(@list) <= 1) {
		return @list;
	} else {

		my $middlin = scalar(@list) / 2;

		foreach (0..($middlin - 1)) {
			push @left, $list[$_];
		}

		foreach ($middlin..(scalar(@list) - 1)) {
			push @right, $list[$_];
		}

		@left = mergesort(@left);
		@right = mergesort(@right);

		return &merge(\@left,\@right);
	}
}