Here's an algorithm that performs the operation, in a slightly more Perl-ish manner (heavy use of shift), but destroys the copies of the lists. It could easily be modified not to do so, by using a list of array offsets, but this should give you a start. In any case, it's just a heck of a lot easier in Perl to shift and always check the first element than to try to keep track of a list of array offsets.

I don't know if it's optimal, but I'm happy with it:

use Data::Dumper;

my @sets =
    ([ 0, 1, 2, 3,          7, 8, 9, 10, 11, 12, 13, 14, 15,     ],
     [ 0,       3,          7, 8,    10, 11,     13, 14,     16, ],
     [ 0, 1, 2, 3,    5,    7, 8,    10, 11, 12, 13, 14,     16, ],
     [       2, 3, 4,    6, 7, 8,    10, 11, 12,     14,     16, ],
     [ 0, 1, 2, 3,          7, 8, 9, 10, 11,     13, 14, 15,     ]);

my @common = ();

### helpers
sub max_element {
    my $max = -1;
    for (@sets) {
        $max = $_->[0] if $_->[0] > $max;
    }
    return $max;
}

sub all_the_same {
    my $element;
    for (@sets) {
        if (not defined $element) {
            $element = $_->[0];
        } else {
            return 0 if $element != $_->[0];
        }
    }
    return 1;
}

### main loop
my $done = 0;
while (not $done) {

    foreach (@sets) {
        $done++ if @$_ == 0;
    }

    if (all_the_same()) {
        push @common, $sets[0][0];
        shift @$_ for @sets;
    } else {
        my $max = max_element();
        for (@sets) {
            shift @$_ if $_->[0] < $max;
        }
    }


    ## uncomment these to see how it works step by step:
    # print Dumper(\@sets, \@common), "\n";
    # <STDIN>

}

print "@common\n";
[download]

Here's a pseudocode breakdown of the algorithm, for illustrative purposes.

common_elements ::= empty list;

while all lists are non-empty; do
  if the first elements of all the lists are the same
    add that element to common_elements
  else
    max_element ::= maximum first element of all lists
    foreach list; do
      if first element of list < max_element;
        shift it off the list
  endif
done
[download]

Works kinda like a merge-sort by moving down all the lists in parallel. I don't know if that's what yours is trying to do. I can't quite grok it at the moment. Update: After adding some Dumper statements to your code, it seems like yours is doing a very similar algorithm, as you said, in a very C++ way. I'm not so sure what to think about the last MAIN; statement you have there. ;-)

There is at least one part where code could be improved: the max_element sub could also return information about which arrays had non-maximum elements, so those arrays could easily be shifted. To do this cleanly and efficiently requires more cleverness than I have, however.

HTH,

blokhead