1. Prove by strong induction o n n that mergeSort(A[1 . . . n]), shown in Figure 5.30, indeed sorts its input.
2. Give a recursive algorithm to compute a list of all permutations of a given set S. (That is, compute a list of all possible orderings of the elements of S. For example, permutations({1, 2, 3}) should return {h1, 2, 3i,h1, 3, 2i,h2, 1, 3i,h2, 3, 1i,h3, 1, 2i,h3, 2, 1i}, in some order.) Prove your algorithm correct by induction.
