1. Execute Merge sort on the following array and sort the keys in descending order, assuming ' a ' is the "lowest" letter. Show the state of the merge at each level of recursion as well as the number of the cut/partition being performed. You may follow the same format shown in the lessons. 2. Given that Insertion sort is worst case (n2) and Merge sort is worst case (nlgn) : a. Under what conditions would Insertion sort outperform Merge sort? You can give a concrete example of this and show/plot the growth of the function as a graph. b. Describe scenario(s) in which Insertion sort may be preferable to Merge sort as it is implemented in the pseudocode we discussed in class? 3. Other than speed, what other factors may determine "efficiency" of an algorithm? 4. Find the order of growth of the following recurrence relations using the Substitution Method. a. T(n)=T(3n)+T(32n)+1 b. T(n)=3T(2n)+O(n) 5. Find the order of growth of the following recurrence relations using the Master Method. a. T(n)=9T(3n)+n b. T(n)=3T(4n)+nlgn 6. Can the master method be applied to the following recurrence? Why or why not? T(n)=4T(2n)+n2lgn