Unless i am missing something (which i usually am), why not just sort the results?

@union = sort grep { not $seen{$_}++ } (@union, @array3);
[download]

UPDATE: i think i see what you want now ... let's try using CHARS instead of INTS. In order to have "intelligent" sorting, you have to provide the "intelligence" ... in this case, let's give weights to each of the items we are dealing with:

my @array1 = ([b=>1], [d=>3], [z=>4], [e=>5]);
my @array2 = ([a=>2], [b=>1], [z=>4]);
my @array3 = ([d=>3], [e=>5]);
[download]

my %seen;
my @union = grep { not $seen{$_->[0]}++ } (@array1, @array2);

undef %seen;
@union =
    map  { $_->[0] }
    sort { $a->[1] <=> $b->[1] }
    grep { not $seen{$_->[0]}++ } (@union, @array3);

use Data::Dumper;
print Dumper \@union;
[download]

L-LL-L--L-LL-L--L-LL-L--
-R--R-RR-R--R-RR-R--R-RR
B--B--B--B--B--B--B--B--
H---H---H---H---H---H---
(the triplet paradiddle with high-hat)