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

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 ?

• I think this problem is ill-posed in at least two ways. 1) What is the definition of $\gg$? 2) I don't see how the runtime can be achieved at all without further assumptions. (See my answer.) – Raphael Jul 24 '15 at 6:38

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