bisect intersection

[Robert Bossy]

Hi,

I stumbled into a sorted list intersection algorithm by Baeza-Yates 
which I found quite elegant. For the lucky enough to have a springerlink 
access, here's the citation:
http://dblp.uni-trier.de/rec/bibtex/conf/cpm/Baeza-Yates04

I implemented this algorithm in python and I thought I could share it. 
I've done some tests and, of course, it can't compete against dict/set 
intersection, but it will perform pretty well. Computing union and 
differences are left as an exercise...

from bisect import bisect_left

def bisect_intersect(L1, L2):
    inter = []
    def rec(lo1, hi1, lo2, hi2):
        if hi1 <= lo1: return
        if hi2 <= lo2: return
        mid1 = (lo1 + hi1) // 2
        x1 = L1[mid1]
        mid2 = bisect_left(L2, x1, lo=lo2, hi=hi2)
        rec(lo1, mid1, lo2, mid2)
        if mid2 < hi2 and x1 == L2[mid2]:
            inter.append(x1)
            rec(mid1+1, hi1, mid2+1, hi2)
        else:
            rec(mid1+1, hi1, mid2, hi2)
    rec(0, len(L1), 0, len(L2))
    inter.sort()
    return inter


Cheers
RB