Exercise 6.8.

Consider the following insertion sort algorithm to sort a given

array of n numbers. The first and second numbers are compared; if they

are out of order, they are swapped so that they are in sorted order. Then

the third number is compared with the second; if it is not in the proper

order, it is swapped with the second and then compared with the first.

Iteratively, the kth number is handled by swapping it downward until the

First k numbers are in sorted order. Determine the expected (i.e., average)

number of swaps that need to be made with insertion sort when the input

is a random permutation of n distinct numbers, i.e., the input is equally

likely to be any of the n! permutations.