Oh, yeah, i did mean intersection. Union is even easier. Use the same procedure and ignore duplicate lines that are adjacent. This means you never have more than two lines in memory at once.

The items being sorted on are strings. It seems to me like merging them and sorting them together before scanning to remove dupes would make this slower than the hash approach, especially since I may have to go to disk if the combined size is a couple of million entries or so. I guess I should really bench it.

Sort the lists independently and then do the dupe elimination as part of the merge. And yes with data sets that large going to disk is required. But thats a good thing, you dont want to hold all of those millions of strings in memory at once do you? Using on disk methods you can sort your sets with a disk based file sort tool that will be more efficient than perls generalized in memory routine. Then the merge is order N (ie a single pass over the file).

Actually, iirc you will find most on disk sort tools will have dupe elimination built in.

---
demerphq

my @a = qw( 1 2 3 3 2 );
my @b = qw( 1 4 5 5 4 );
my @c = qw( 1 6 7 7 6 );
[download]

1 2 3 4 5 6 7
[download]

That's right, except the lists are sets, i.e. they have no dupes internally, and they are already individually sorted.