Intersection of sorted lists
While you don't want alternative solutions, you should take a look at the data in your specific usecase. As an example, for some randomly generated input (both lists of length ~600) on my machine (Python 3.6.9, GCC 8.3.0), your function takes

In [18]: %timeit sorted_lists_intersection(a, b)
179 µs ± 1.19 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)


The function defined in the answer by @alexyorke, while more readable IMO, takes a bit longer:

In [16]: %timeit list(intersect(a, b))
249 µs ± 4.67 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)


In contrast, this highly readable and short implementation using set and sorted, that completely disregards the fact that the lists are already sorted (which means that it also works with unsorted lists):

def intersect_set(a, b):
    return sorted(set(a) &amp; set(b))


is about twice as fast:

In [29]: %timeit intersect_set(a, b)
77 µs ± 1.44 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)


Of course, in order to properly compare them, here are more data points:

import numpy as np

np.random.seed(42)

ns = np.logspace(1, 6, dtype=int)
inputs = [[sorted(set(np.random.randint(1, n * 10, n))) for _ in range(2)] for n in ns]


The set based function wins in all of these test cases:



It looks like for lists with lengths of the order of more than 10M your function might eventually win, due to the \$\mathcal{O}(n\log n)\$ nature of sorted.

I think the greater speed (for a wide range of list sizes), coupled with the higher readability, maintainability and versatility makes this approach superior. Of course it requires objects to be hashable, not just orderable.

Whether or not this data is similar enough to yours, or whether or not you get the same timings, performing them to see which one is the best solution in your particular usecase is my actual recommendation.