Fastest Algorithm for "Merge" step in Mergesort

Question

Given two sorted arrays $a_1,a_2,\dots,a_n$ and $b_1,b_2,\dots,b_m$, merge them together into one sorted array $c_1,c_2,\dots,c_{n+m}$ containing the elements of $a$ and $b$.

The typical mergesort method works in $O(n+m)$, and if we run binary search for each element from one of the arrays, it works in $O(\min(n,m)\log(\max(n,m)))$. However, the latter method is no better than if the smaller array was unsorted. I was wondering if there is any use of the fact that both arrays are sorted to optimise the latter solution. In particular, I was hoping for an algorithm in time $O(\min(n,m))$ or so.

I attempted a "parallel binary search" method, but it seems in the worst case that it is no better than the naive binary search method.

Answer 1

If you only want to count the number of comparisons then you can achieve $O\left(n\log(1+\frac{m}{n})\right)$ comparisons as follows:

Let $k_1$ denote the index of $a_1$ in the final array $c$ and for $1<i\leq n$ let $k_i$ denote the difference between the indices of $a_i$ and $a_{i-1}$ in the final array $c$.

To insert $a_1$ in $b$, start by doing an exponential search to find the smallest $r$ such that $b_{2^r} \geq a_1$ (this is also the smallest $r$ such that $2^r \geq k_1$). This takes $O(\log k_1)$ comparisons. Now do a binary search between the indices $1$ and $2^r$ to locate the correct position $k_1$ to insert $a_1$, and insert the element there. This also takes $O(\log k_1)$ comparisons.

To insert $a_2$ into $b$ start by doing an exponential search, starting at $k_1$, to find the smallest $r$ such that $b_{k_1+2^r} \geq a_2$ (this is also the smallest $r$ such that $2^r \geq k_2$). This takes $O(\log k_2)$ comparisons. Now do a binary search between the indices $k_1$ and $k_1+2^r$ to locate the correct position $k_1+k_2$ to insert $a_2$, and insert the element there. This also takes $O(\log k_2)$ comparisons.

In general following this strategy you will make $O(\log k_i)$ comparisons to insert element $a_i$. So the total number of comparisons will be $T = O\left(\sum_{i=1}^n\log k_i\right)$. Because the $\log$ function is concave, by Jensen's inequality we have $\sum_{i=1}^n\log k_i \leq n\log \frac{\sum k_i}{n} \leq n\log \frac{n+m}{n}$. The result follows.

Notice that (assuming $n\leq m$) this is asymptotically always at least as good as $O(n+m)$ and $O(n\log m)$, and sometimes better than both: if you take for example $m=n\log n$ you get $O(n\log\log n)$ comparisons compared to $O(n\log n)$ with both other methods.

To complement this, let us show that this is optimal (up to a constant factor, still assuming $m\geq n$). The number of ways to insert $n\geq 1$ ordered elements into an ordered array of length m is $\frac{(m+n)!}{m!n!} \geq \frac{(m+1)^n}{n!} \geq \max\{(\frac{m}{n})^n, 2^n\}$. Thus to distinguish between these cases you need at least $T\geq \log_2(\frac{(m+1)^n}{n!})$ comparisons in the worst case. We have $T \geq \max\{n\log_2\frac{m}{n}, n\}$, which implies $T \geq \frac{1}{2}n\log_2(1+\frac{m}{n})$.

Answer 2

One method fitting the analysis results presented is
one by one, insert elements of the shorter sequence ($s$) in the longer one ($l$).

There are several way to reduce the search range in the longer sequence exploiting the shorter one to be ordered, too, starting with

position ← 0
for every element $e$ of $s$
   position ← insertion position of $e$ in $l$, starting from position
   insert $e$ in $l$ at position

— without any relation specified between $n$, $m$, and the values in $a$ and $b$, I don't see any to allow a tighter bound on time than
$O(\min(n,m)\log(\max(n,m)))$.

Try proving $O(n+m)$ is optimal.

Answer 3

The purpose of a merge is to form a single, continuous array holding the $n+m$ keys from the original arrays.

Even if everything can be done in-place (by $a$ and $b$ being contiguous), in the worst case you need to move all of them, which is $\Omega(n+m)$. Hence a merge in time $O(n+m)$ is optimal.

Even ignoring the moves (?), in the worst case you need to look at all keys at least once, and $O(n+m)$ is still optimal.

---

A light of hope: the best case is more promising. If $a, b$ are contiguous and $a_n<b_1$, the merge can be done in $O(1)$.