data structure

1 a.|Trace bottom-up merge sort (see class notes for implementation details) with the following input, where merge result with sz-k should contain the result of merging adjacent sub-arrays each with size of k. The last row should contain the final sorted result. Index 0 Input 342 773429 966 19 Merge Result SZ=1 Merge Result sz = 2 Merge Result 4 952 711 133 684 143 Merge Result Sz 8 b. Does the merge method produce the proper output if two input subarrays are not in sorted order? Prove your answer or provide a counter example c. Give the sequence of subarray sizes in top-down merge sort forN-10