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;
You can do some time measurements with your real data to see if this gains you anything or not.