1. (a) (6 points) Suppose you have some procedure FASTMERGE that given two sorted lists of length m each, merges them into one sorted list using mc steps for some constant c > 0. Write a recursive algorithm using FASTMERGE to sort a list of length n and also calculate the run-time of this algorithm as a function of c. For what values of c does the algorithm perform better than O(n log n).

2. (b) (4 points) Let A[1 . . . n] be an array such that the first n n elements are already in sorted order. Write an algorithm that will sort A in substantially better than O(n log n) steps.