I would divvy the arrays up into records separately from the matching part.

# Divide @arr into records, store in %harr.
my %harr;
my $j = 0;
while ($j+2 < scalar(@arr))
{
    my $rec = [ @arr[$j .. $j+2] ];
    push @{$harr{ $rec->[0] }}, $rec;
    $j += 3;
}

# Divide @arr2 into records, store in %harr2.
my %harr2;
$j = 0;
while ($j+3 < scalar(@arr2))
{
    my $rec = [ @arr2[$j .. $j+3] ];
    push @{$harr2{ $rec->[0] }}, $rec;
    $j += 4;
}

# Munge
foreach my $key (sort {$a<=>$b} keys %harr2)
{
    print "@$_\n" foreach @{$harr2{$key}};
    print "@$_\n" foreach @{$harr{$key}};
    print "\n";
}
[download]