This is the problem:
Merge two sorted series of numbers. Their lengths are $n$ and $m$, respectively, but $n \gg m$. Your algoritm should take $O(m \log(n/m))$ comparisons.
I have come up with this algorithm:
1. Choose n/m "special" elements among n elements. 2. for i = 1 to m do 2.1 Using binary search find block (between two special elements) where m_i should be inserted - time O(log(n/m)) 2.2 Using binary search in found block, find exact position for $m_i$. - O(log m)
Step 2.1 takes time $O(\log(n/m)$ and step 2.2 time $O(\log m)$, so I get in total a runtime in $O(m (\log n/m + \log m))$. How do I get rid of the $O(\log m)$ term?
Here's a sketch of the algorithm:
As you can see I have a problem - O(log m). How to eleminate it ?