1. Insertion-sort can be expressed as a recursive procedure as follows. In order to sort A[1..n], we recur- sively sort A[1..n 1] and then insert A[n] into the sorted array A[1..n 1].

(a) Describe this recursive version of insertion-sort in pseudocode.

(b) Write a recurrence relation for the running time of this recursive version of insertion-sort. Solve

this recurrence relation. Express your final answer in terms of O-notation.

2. Inversions. Let A[1..n] be an array of n distinct numbers. If i < j and A[i] > A[j], then the pair

(i, j) is called an inversion of A.

(a) List the five inversions of the array < 2, 3, 8, 6, 1 >.

(b) What array with elements from the set {1, 2, . . . , n} has the most number of inversions? How many does it have?

(c) What is the relationship between the running time of insertion sort and the number of inversions in the input array? Justify your answer.

(d) Give an algorithm that determines the number of inversions in any permutation of n elements in O(n log n) worst-case running time. (Hint: Modify Merge-sort.)