It assumes that each element is unique in a given array

Is that the case for your arrays? If not, it would explain the difference.

Update: See almut's reply below, this code is nonesense.

(Update:) I'd just store one array in the hash, something along these lines: (untested)

my (@intersection, @union);
my %count;
@count{@array1} = undef;
for (@array2) {
    if (exists $count{$_}) {
          push @union, $_;
    } else {
          push @intersection, $_;
    }
}
[download]

(Second update): Any idea why the answer in the FAQs makes such an IMHO needless assumption? The code without that assumption isn't much longer, and although I haven't benchmarked it I don't think it's much slower either (I even think it uses less memory).

Any idea why the answer in the FAQs makes such an IMHO needless assumption?

I think your code doesn't compute the difference, and the union also isn't what you'd normally define as union (even if you swap @intersection and @union)...

my @array1 = qw(foo foo bar baz);
my @array2 = qw(bar grmpf asdf);

my (@intersection, @union);
my %count;
@count{@array1} = undef;
for (@array2) {
    if (exists $count{$_}) {
          push @union, $_;
    } else {
          push @intersection, $_;
    }
}

use Data::Dumper;
print Dumper \@intersection, \@union;

__END__
$VAR1 = [
          'grmpf',
          'asdf'
        ];
$VAR2 = [
          'bar'
        ];
[download]

Yes, you're totally right. If one allows duplicates, the union is just @union = @array1, @array2.