Yes, its a quite an interesting problem and solved using parallel
programming many times.
I think the idea , as Ercan thought of, is to do a binary search.
Consider 2 arrays A and B.
Divide both arrays into logn sizes blocks.
For each block let the first element be the head element. Now cross
does not seem possible, there is a proof that shows that comparison
based algorithm can have at best O(nlogn) worst case running time. You
can check this proof from algorithms CLRS book.
Using this proof, by master's theorem if the merge operation can be
implemented in O(lgn) using merge sort
No. It is possible.
This problem focuses on comparisons of each element.
The overall time complexity of merge operation can be as high as O(nlogn),
while the normal merge operation has time complexity O(n).
But the normal merge operation does not meet the requirement, since in
the worst case,
Ok I see your point, I thought that it asked to provide an algorithm
with overall complexity O(logn), which is not possible.
why not use a binary search like procedure to fix the worst case.
Choose the array lets say list L with the bigger number, then instead
of checking each element of smaller
