If the arrays are already sorted, it might be a pity to lose that information and have to re-sort at the end though. You might consider doing a standard merge instead:

my @baz;
my $f = $b = 0;
while ($f < @foo && $b < @bar) {
    my $cmp = $foo[$f][0] cmp $bar[$b][0];
    push @baz, [$cmp <= 0 ?  @{$foo[$f++]} :
                            (@{$bar[$b]}[0, 1], undef),
                $cmp >= 0 ? $bar[$b++][-1] : undef];
}
push @baz, [@{$foo[$_]}, undef] for $f..$#foo;
push @baz, [@{$bar[$_]}[0, 1], undef, $bar[$_][-1]] for $b..$#bar;
[download]

You can do some time measurements with your real data to see if this gains you anything or not.