0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ (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.)) $\endgroup$
    – greybeard
    Jan 31 at 8:59
  • $\begingroup$ 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$. $\endgroup$ Mar 3 at 9:20

3 Answers 3

1
$\begingroup$

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

$\endgroup$
0
0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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). $\endgroup$
    – Tassle
    Mar 2 at 13:36
  • $\begingroup$ @Tassle You may have missed the problem statement specifying a 3rd/output array $c_1,c_2,…,c_{n+m}$. $\endgroup$
    – greybeard
    Mar 4 at 9:48
0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Tassle
    Apr 2 at 14:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.