Merge two series of sorted number, one much longer than the other

Question

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 ?

Answer 1

What exactly does $n \gg m$ mean for your professor?

If it means $m \in o(n)$, then you are allowed $O(\log m)$ time for step 2.2. Note that $\log(n/m) = \log n - \log m$. If $m \in o(n)$, the target runtime bound simplifies to $O(m \log n)$; a summand $m \log m$ is dominated by this.

If $m \in \Theta(n)$ is allowed -- arguably, $m = n \cdot 10^{-10}$ would fulfill "a lot smaller" -- you can have that $\log n/m \in O(1)$ and the runtime bound is $O(m)$. It's quite clearly impossible to perform this task in time $O(m)$, so I think we can safely ignore this case for the purpose of this exercise.

But here is something more for you to think about.

In step 1, you need to specify "special"; if you don't pick the elements according to your sketch, the rest won't work out. So we have to select the elements $i(n/m)$. In order to do this in $o(n)$ time and perform binary search efficiently, we need the series to be stored as arrays.

We can not copy all values to a new array in the required time. We can not insert values into an array, either. So how is this to work at all?