5
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • 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
8
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\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
3
$\begingroup$

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.)

|cite|improve this answer
$\endgroup$
  • $\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
1
$\begingroup$

Hint: You can implement an algorithm similar to merge sort in order to find the instersection. It takes $O(n)$ time.

|cite|improve this answer
$\endgroup$
  • 2
    $\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
  • $\begingroup$ @Raphael But if I have written this, I would've basically given the answer, wouldn't I? $\endgroup$ – padawan Nov 10 '16 at 17:15
  • 2
    $\begingroup$ Yes. Sometimes giving a good hint is harder than just giving the answer. $\endgroup$ – Raphael♦ Nov 10 '16 at 17:15

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.