1. 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	1	2	3	4	5	6	7	8	9
Input	342	773	429	966	19	952	711	133	684	143
Merge Result sz = 1
Merge Result sz = 2
Merge Result sz = 4
Merge Result sz = 8

2. 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.

3. Give the sequence of subarray sizes in top-down merge sort for N=10.