Say that there are two sorted lists: A and B.

The number of entries in A and B can vary. (They can be very small/huge. They can be similar to each other/significantly different).

What is the known to be the fastest algorithm for this functionality?

Can any one give me an idea or reference?

  • $\begingroup$ Hint: You can implement an algorithm similar to merge sort in order to find the instersection. It takes $O(n)$ time. $\endgroup$ – padawan Nov 10 '16 at 12:35
  • 1
    $\begingroup$ "Fastest" how, on which machine? What kind of list implementation do we have? What have you tried and where did you get stuck? $\endgroup$ – Raphael Nov 10 '16 at 17:13
  • $\begingroup$ I find this hint misleading. The algorithm is not "similar to mergesort" but literally the merge algorithm used in mergesort. $\endgroup$ – Raphael Nov 10 '16 at 17:13

Hwang and Lin's Algorithm (A simple algorithm for merging two disjoint linearly-ordered sets (1972) by F. K. Hwang , S. Lin) is the reference on how to merge (or intersect) ordered lists of unequal sizes with (possibly) fewer comparisons. It works by calculating a stride from the ratio m/n and doing the comparison against that element in the larger list; for instance if m/n = 4 it will compare the fourth element of the larger list against the first of the other, and either eliminate all 4 elements or do a binary search within them for the correct insertion/intersection point.

It neatly covers the continuum from merging equal-sized lists with the usual algorithm to merging a list of one element into a list of n with a single binary search.

  • $\begingroup$ Download links seems dead... any other way to get the (free) paper? $\endgroup$ – maxik Nov 11 '16 at 7:43
  • $\begingroup$ I noticed that as well -- it's intermittent though. I put the full title in so that you can search for it if needed. $\endgroup$ – KWillets Nov 11 '16 at 15:50

Essentially the same algorithm as you'd use to merge the two lists. In the general case, you can't possibly do better than looking at essentially every element of both lists because, if you don't look at the elements, you don't know what's in the lists, so you don't know what's in the intersection. (OK, you can stop as soon as you've run out of elements in one of the lists but, if the biggest element of both lists is the same, you'll have read everything.)

  • $\begingroup$ You don't need to look at every element in both lists: consider the case where one list has 1 element and the other N elements - you can find the intersection via binary search after examining only log(N) elements in the larger list. So the complexity is definitely better than you suggest when one list is much smaller than the other. $\endgroup$ – BeeOnRope Apr 3 '19 at 22:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.