Merge k sorted arrays of exponentially increasing lengths
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 &lt; 2\cdot 2^k + C(T^-) &lt; 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.