A common way to solve this is to sort both lists. Then you can alternately advance through each list to see what items are in both, in just the first, or in just the second.

For example:

#!/usr/bin/perl -w

use strict;

my @red_things = qw(apple little_corvette strawberry lava);
my @fruits = qw(apple pineapple strawberry banana);

my @sorted_red_things = sort @red_things;
my @sorted_fruits = sort @fruits;

while (@sorted_red_things || @sorted_fruits)
{
  my($thing,$fruit)=($sorted_red_things[0],$sorted_fruits[0]);
  if (defined($thing) and (!defined($fruit) or ($thing lt $fruit)))
  {
    print "A red thing that's not a fruit: $thing\n";
    shift @sorted_red_things;
  }
  elsif (!defined($thing) or ($thing gt $fruit))
  {
    print "A fruit that's not red: $fruit\n";
    shift @sorted_fruits;
  }
  elsif ($thing eq $fruit)
  {
    # It's in both lists
    shift @sorted_red_things;
    shift @sorted_fruits;
  }
}
[download]

You can sort into files to conserve memory.

The runtime of this will be pretty good. Total time is time to sort first list + time to sort second list + time for scan, which is O(n lg n + n lg n + 2n) = O(n lg n).