a. (1,5), (2,5), (3,4), (3,5), (4,5)
b. If the array is in nonincreasing order, then the number inversion are n(n-1)/2
c. Each element movement can decrease one inversion.
d. The same as merge sort. Suppose that we have two sorted array’s inversion numbers, let the array be L and R. Then what are the number of inversions between R and L. If R[j] <L[i], then R[j] incurs |L| – i + 1 inversions. We can count the inversion in the merge phase.
a. Θ(n)
b.
y = 0
i = 0
while i ≤ n
j = 1
z = 1
while j ≤ i
z = z * x
j = j + 1
y = y + ai * z
i = i + 1
return y
c.
d. By c, it is obviously.
a. A’ must be a permutation of A.
b. Loop invariant: A[j] is the minimum value of A[j]~A[n].
c. Loop invariant: A[1]~A[i] is the smallest i numbers in A, and A[1]~A[i] is in sorted order.
d.
a. Insertion sort’s worst case running time is 
b. The merge can be done in Θ(n) time. But we should merge lists with the same length. We can merge all lists with length k, then get all lists with length 2k. And repeat this process until there is only one list. Every iteration takes Θ(n) time, and there are at most Θ(lg(n/k)) iterations. So the running time is Θ( n lg(n/k) ).
c. If k = Θ(lg n), then the running time is Θ(n lgn).
d. Choose the largest k such that insertion sort runs faster then merge sort.
Solution 1: Sort the set first. For any element y in S, use binary search to determine whether there is one element z in S-y such that y + z = x. Since the binary search can be done Θ(lg n), the overall running time is Θ(n lgn).
Solution 2: Sort the set first. Let 
No. Although the comparisons are Θ(n lgn), but the data movements are still
Base case: n = 2, T(n) = 2.
Induction step: Assume that T(n) = n lg n for all n = 
Eliminate step 8 and 9.
For step 12~17, add the condition that 
