0
$\begingroup$

Is there a faster algorithm to merge two sorted linked lists where one is guaranteed to be much larger than the other?

By merging two sorted lists I mean taking two sorted lists $A$ and $B$ and producing a new list that contains all the elements of $A$ and $B$ and is sorted itself.

The typical solution, which Wikipedia lists and I have written in Haskell below, is $O(n+m)$

merge :: (Ord a) => [a] -> [a] -> [a]
merge [] [] =[]
merge a@(_:_) [] = a
merge [] b@(_:_) = b
merge (a : ax) (b : bx)
 | a <  b = a : merge ax (b : bx)
 | a >= b = b : merge (a : ax) bx

However simply inserting each element of the shorter list into the longer one using binary search is $O(n\log m)$1, which when $n \ll m$ is considerably better than $O(n + m)$. This doesn't even use the fact that the smaller list is already sorted which may be leveragable for better speeds.

Are there a faster algorithms to merge two sorted lists where one is much larger than the other?


It has now been pointed out that I was incorrect about this, it cannot be done that fast because we to walk through the list for binary search.

$\endgroup$
5
  • 2
    $\begingroup$ How are the lists presented on the input? If they are presented as linked lists, you can't do better than $O(n+m)$, as you need to read the entire list to solve the problem, and in particular, you can't achieve $O(n \log m)$ time when they're represented as linked lists. Please specify how they are represented. If they are represented with some other data structure (a balanced binary tree?), please indicate that in the question. $\endgroup$
    – D.W.
    Apr 25, 2018 at 20:35
  • $\begingroup$ @D.W. They are in fact linked lists. I've made that clear. $\endgroup$ Apr 25, 2018 at 21:05
  • $\begingroup$ The problem is not really that you need to copy the list, but as D.W. indicates, in order to get anywhere inside the list you have to walk through it. That's how linked lists work. In other words, binary search is impossible on linked lists. $\endgroup$ Apr 25, 2018 at 21:11
  • $\begingroup$ Binary search ? How ?? $\endgroup$
    – user16034
    Jan 4, 2023 at 14:10
  • $\begingroup$ You can do binary search, but it takes m operations skipping from one item to another, and log m comparisons. Still much faster than m comparisons, especially if going from one item to the next is fast and comparisons are slow. But not asymptotically faster. $\endgroup$
    – gnasher729
    Jan 4, 2023 at 14:50

2 Answers 2

1
$\begingroup$

If by "faster" you mean in terms of number of comparisons (so walking the list just to find an index doesn't matter) or if you weren't using linked lists, then yes there are faster algorithms. Specifically in cases where as you said, one list is guaranteed to be "much" longer than the other.

This paper gives an algorithm for lists where $n/m > 8$. I don't understand it well enough to summarize, sorry.

Timsort takes inspiration from ideas like that and applies them to real world data when merging runs in "galloping mode". He explains the logic in a bit more detail in the original explanation (under "Merge Algorithms").

$\endgroup$
1
$\begingroup$

Assume two sorted lists A and B with n and m elements, where n is much smaller than m.

First, it will be faster if you can modify B, because most of the links between list elements are correct and don't need changing. If you create a new list, you have to set up n+m connections correctly. But anyway, do your list items support being in multiple lists? (Not if each item just has a "next" field)? If not, then you modify B.

Second, is there a way to access arbitrary items in constant time? Being a list, there should be no way to do this. So binary search doesn't help much - you still need to follow m links so the time is linear.

Assuming n is much smaller, and comparisons are slower than going through a linked list: Normally you would iterate through the list B until you find an item less than an item of A, then you insert that item, and so on. Initially you would skip say m / 4n items. Iterating through the list should be fast (just following a link), but there are much less than M comparisons.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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