# Merge k sorted arrays of exponentially increasing lengths

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.

• 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. – D.W. Feb 29 '16 at 19:24

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.