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.