Intersection of sorted lists I don't like this function. Looks too imperative.

It takes two sorted lists and returns a sorted intersection of the two lists. There is an implicit assumption that there are no duplicate elements in either list.

Please don't suggest converting (even one of) the arguments to set, or using some sort of library function. This is a single-pass O(n+m) time, O(1) auxiliary space algorithm, and I want to keep it that way.

def sorted_lists_intersection(lst1, lst2):

  i1 = 0
  i2 = 0
  len1 = len(lst1)
  len2 = len(lst2)

  intersection = []

  while i1 &lt; len1 and i2 &lt; len2:

    while lst1[i1] &lt; lst2[i2]:
      i1 += 1
      if i1 == len1:
        return intersection

    while lst2[i2] &lt; lst1[i1]:
      i2 += 1
      if i2 == len2:
        return intersection

    if lst1[i1] == lst2[i2]:
      intersection.append(lst1[i1])
      i1 += 1
      i2 += 1

  return intersection
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.