Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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.
