1. How would you implement mergesort without using recursion?
2. Determine the running time of mergesort for
a. sorted input
b. reverse-ordered input
c. random input
2. In the analysis of mergesort, constants have been disregarded. Prove that the number of comparisons used in the worst case by mergesort is Nflog N1-2flog N1+1.