In this problem you will explore two algorithms for the problem of merging k sorted arrays, each containing n elements, into a single sorted array containing nk elements. The cost of merging an array of size a with an array of size b is a+b.
O The first algorithm merges two of the arrays, then merges in the third array, then merges in the fourth array, and so on.
1. We start by merging together two of the k arrays together, producing array M2. What is the cost of this merge?
2. We merge another of the k arrays with M2 from the previous question, producing M3. What is the cost of this merge?
O Now we'll consider a second algorithm. We are given k n-element arrays to merge. We recursively merge the first k/2 arrays, recursively merge the second k/2 arrays, and then merge the two results.
3. Imagine the recursion tree that results from this. We are sitting at the root of the tree. What is the cost of the merge done at the top of the tree?
4. What is the total cost of the two merges done at the second level of the tree?