Given two lists [T], the following algorithm finds the intersection (values common to both lists) in O(min(m, n)) time and O(min(m,n)) space provided that:
def intersection(A, B): a = len(A) s = 0 R =  for n in B: for i in range(s, a): c = A[i] if n < c: break s += 1 if n == c: R.append(n) break if s == a: break return R
Another algorithm for when intersections should be found in place. This modifies A. Most of the ugliness from the code stems from the fact that it is hard to iterate backwards in Python. Again all conditions from the first algorithm need to be satisfied. However:
def intersection(A, B): b = len(B) - 1 a = len(A) - 1 # Find intersections, and set a to be the index # where the algorithm should search from for i in range(b, -1, -1): n = B[i] for j in range(a, -1, -1): c = A[j] if n > c: break a -= 1 if n == c: break del A[j] # everything below a is not included in the other # set, so delete for j in range(a, -1, -1): del A[j] return A
Both algorithms exploit the fact that the lists are already sorted, and break from the inner loop early to avoid a full scan whenever it makes sense to avoid O(mn). It is possible to use a binary search instead of the linear scan to determine the index.
However, that would give a worse time complexity should the lists have very tighly clustered values: linear search is at worse, O(n) but Ω(1). However a binary search is almost always O(log n). Case in point:
Easy to find 1 in [1,2,3,4,5,6,7,8] using linear search. However a binary search needs ~3 steps.