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.
