Lopsided merge algorithms

Question

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)$¹, 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.}

Answer 1

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

Answer 2

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.