Fastest Algorithm for "Merge" step in Mergesort

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.

• (The typical mergesort method should read The typical merge method more likely than not. In a scientific context, it is challenging to ask for optimal solutions (Fastest Algorithm): any proposal will be expected to be proven. (Which is where within a constant factor comes in.)) Commented Jan 31, 2022 at 8:59
• What makes you think that $\min(n,m)\log(\max(n,m))$ would be any better than $n+m$ ? Take $n<m$ WLOG and divide both functions by $m$. Now you compare $\dfrac nm\log m$ and $\dfrac nm+1$.
– user16034
Commented Mar 3, 2022 at 9:20

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 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})$$.

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.

• Well supposing $n\leq m$ (just to make it more readable) you can always have $O(\min(n\log m, n+m))$ comparisons: start with the binary search method and if you have reached $n+m$ comparisons finish with the "typical" method (or even start over from scratch with this method). Commented Mar 2, 2022 at 13:36
• @Tassle You may have missed the problem statement specifying a 3rd/output array $c_1,c_2,…,c_{n+m}$. Commented Mar 4, 2022 at 9:48

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, the merge can be done in $$O(1)$$.

• If you're only interested in comparisons $O(n+m)$ is not always optimal (say if $m$ is large compared to $n$, then the binary-search strategy does $O(n\log m)$ comparisons and doesn't need to look at all the keys in the array $b$). See my answer for what I think is the true optimum in that setting. Commented Apr 2, 2022 at 14:10