Design an algorithm for merging on a tree-connected SIMD computer. The two input sequences to be merged, of length r and s, respectively, are initially distributed among the leaves of the tree....

Design an algorithm for merging on a tree-connected SIMD computer. The two input sequences to be merged, of length r and s, respectively, are initially distributed among the leaves of the tree. Consider the two following situations: (i) The tree has at least r + s leaves; initially leaves I,...,r store the first sequence and leaves r + 1, . . ., r + s store the second sequence, one element per leaf. (ii) The tree has fewer than r + s leaves; initially, each leaf stores a subsequence of the input. Analyze the running time and cost of your algorithm.