Given a sequence a1 , a2 , . . . , an of n distinct numbers, an inversion is a pair i < j such that ai > aj . Note that a sequence has no inversions if and only if it is sorted in ascending order.

A variant of merge sort algorithm for counting inversions as follows:

Sort-and-Count(L) {

if list L has one element

return 0 and the list L

Divide the list L into two halves A and B

(rA, A) Sort-and-Count(A)

(rB, B) Sort-and-Count(B)

(rt, L) Merge-and-Count(A, B)

return r = rA + rB + rt and the sorted list L

Write the pre-post conditions and pseudo code for Merge-and-Count(A, B).

}