If the lists are actually sorted (as in your examples), especially if the lists could be very large, a merge might be a good choice. Anyone have a more idiomatically Perl way of writing a merge that doesn't copy nor modify the original lists?

my @old= ( 1, 2, 4, 5, 6, 8, 15 );
my @new= ( 1, 3, 4, 5, 6, 7, 9 );
my( $i, $j )= ( 0+@old, 0+@new );
my( @add, @del );
while(  $i  ||  $j  ) {
    if(  ! $j  ||  $i  &&  $new[$j-1] < $old[$i-1]  ) {
        push @del, $old[--$i];
    } elsif(  ! $i  ||  $j  &&  $old[$i-1] < $new[$j-1]  ) {
        push @add, $new[--$j];
    } else {
        $i--;   $j--;
    }
}
print "del: @del\n";
print "add: @add\n";
__END__
del: 15 8 2
add: 9 7 3
[download]

        - tye (but my friends call me "Tye")