Answer the following questions for the Merge Sort Algorithm

i. How is the division of an array/subarray done by the algorithm during the partition step?

ii. How many recursive steps are required by this algorithm to reach the base case (= an

array with one element)?

iii. Use the Big-O notation to estimate the number of comparisons done by this algorithm at

each level of the recursive tree.

iv. Is merge sort algorithm in-place?

v. What are the recurrence relations for the best, average and worst cases of this algorithm?

vi. Use the Big-O notation to provide running times for the best, average and worst cases of

this algorithm.

vii. Provide an input and select the pivot point to get the worst case.

viii. Provide an input and select the pivot point to get the best case.