#!/usr/bin/perl -w

use strict;

use v5.10;

use Time::HiRes 'tv_interval', 'gettimeofday';

sub linear_merge_slow {

my @a = @{(shift)};

my @b = @{(shift)};

my @c;

push @c, $a[0] < $b[0] ? shift @a : shift @b while @a and @b;

return @c, @b, @a;

}

sub linear_merge_fast {

my @l1 = @{$_[0]};

my @l2 = @{(shift)};

my ($lp1, $lp2, $ll1, $ll2, @l) = (0, 0, $#l1, $#l2);

while ($lp1 < $ll1 and $lp2 < $ll2) {

if ($l1[$lp1] < $l2[$lp2]) {

push @l, $l1[$lp1];

$lp1++;

} else {

push @l, $l2[$lp2];

$lp2++;

}

}

return @l, $lp1 < $ll1 ? @l1[$lp1..$ll1] : @l2[$lp2..$ll2];

}

# no need for srand, perl does it for us

my $a = int rand 1000;

my $b = int rand 1000;

my @a = $a .. $a + 200000;

my @b = $b .. $b + 200000;

my $start = gettimeofday;

linear_merge_fast \@a, \@b;

my $fast = gettimeofday - $start;

say "fast merge took $fast seconds";

$start = gettimeofday;

linear_merge_slow \@a, \@b;

my $slow = gettimeofday - $start;

say "slow merge took $slow seconds";

say "slow seems to be about ", ($slow / $fast), " times slower than fast";

say "sanity tests";

say join ',', linear_merge_fast [1, 7, 9], [2, 3, 9, 9];

say join ',', linear_merge_slow [1, 7, 9], [2, 3, 9, 9];

say join ',', linear_merge_fast [1, 1, 1], [9];

say join ',', linear_merge_slow [1, 1, 1], [9];