0
$\begingroup$

I've seen many answers to merge identical-sized arrays, but haven't seen the answer to this question yet.

Given $A_1, A_2, ..., A_k$ sorted arrays where $|A_i| = 2^i$, what is the most efficient way to merge them all? I'm looking for a comparison-based algorithm with the best asymptotic running time possible.

$\endgroup$
  • 3
    $\begingroup$ Hello! We discourage posts that simply state a problem out of context, and expect the community to solve it. What have you tried? Where did you get stuck? We do not want to just do your exercise for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. $\endgroup$ – D.W. Feb 29 '16 at 19:24
3
$\begingroup$

We can describe any merging algorithm in a tree form (each internal node corresponds to a merged array). Suppose that the cost of merging two arrays $B,C$ is exactly $|B|+|C|$. Then the total cost equals $\sum_{i=1}^k d_i |A_i|$, where $d_i$ is the depth of the leaf $A_i$.

Consider now an arbitrary merge tree $T$. Suppose that $A_k$ is not a child of $T$. In that case, we can form a new tree $T'$ as follows: let $T^-$ be $T$ with $A_k$ removed (and its sibling promoted to its father), and let $T'$ be the tree with children $A_k$ and $T^-$. The cost of $T'$, denoted $C(T')$, satisfies $$ C(T') = 2^k + C(T^-) + \sum_{i=1}^{k-1} 2^i < 2\cdot 2^k + C(T^-) < C(T). $$ Here $2^k$ is the cost of $A_k$ and $\sum_{i=1}^{k-1} 2^i$ is the additional cost of all other leaves (since they are all one level deeper).

We conclude that $A_k$ must be merged last. Continuing this way, we see that the optimal schedule merges $A_1,A_2$, merges the result with $A_3$, merges the result with $A_4$, and so on.

$\endgroup$
  • $\begingroup$ I'd guess the cost closer to max(|B|, |C|). $\endgroup$ – greybeard Apr 30 '16 at 7:44
  • $\begingroup$ @greybeard That's the same up to a factor of two. $\endgroup$ – Yuval Filmus Apr 30 '16 at 8:24

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.