You could do:

my @array1 = (1,2,3,4,5);
my @array2 = (4,5,6,7,8);

@union = @intersection = @difference = (); 
%count = (); 
foreach $element (@array1, @array2) { $count{$element}++ } 
foreach $element (@array1, @array2) {
    if (exists $count{$element}) {
        push @union, $element; 
        push @{ $count{$element} > 1 ? \@intersection : \@difference }
+, $element;
        delete $count{$element};
    }
}

print "Union:        @union\n";
print "Intersection: @intersection\n";
print "Difference:   @difference\n";
[download]

Output:

Union:        1 2 3 4 5 6 7 8
Intersection: 4 5
Difference:   1 2 3 6 7 8
[download]

Update: as to the incorrect difference (as pointed out by ikegami): the OP said "it's perfect for what i need, except for ... the order", so I didn't consider it my business to redefine his/her notion of "difference", but rather just modify the code to keep the original ordering...