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.

  • 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 '18 at 20:35
  • $\begingroup$ @D.W. They are in fact linked lists. I've made that clear. $\endgroup$ – Sriotchilism O'Zaic Apr 25 '18 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$ – Albert Hendriks Apr 25 '18 at 21:11

Your Answer

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

Browse other questions tagged or ask your own question.