The Insertion Sort algorithm is as follows:

Input: An array A=[a_1,a_2,...,a_n] of n elements

Output: The array A in sorted order for i=2 to n Initialize j=i

while(j>1 & A[j-1] > A[j])

swap A[j-1] andA[j]

set j=j-1

Return A

In this problem we will do a finer analysis of Insertion Sort and show that it runs fast on nearly sorted data.

1. An inversion in an array A = [a1, a2, . . . , an] is a pair (ai , aj ) such that i < j but ai > aj . For example, in the array [4, 2, 5, 3] there are three inversions. A sorted array has no inversions, and more generally, the number of inversions is a measure of how well-sorted an array is. Prove that after every comparison made by Insertion Sort, the number of inversions in the array decreases by at most 1.

2. Lower bound: Based on part 1, prove that the Insertion Sort algorithm, when given as input an array A of n elements and having I inversions, must perform at least I comparisons.

3. Prove that after every comparison made by Insertion Sort, either the number of inversions in the array decreases by 1 or the loop variable i (see the algorithm above) increases by 1.

4. Upper bound: Based on part 3, prove that the Insertion Sort algorithm, when given as input an array A of n elements and having I inversions, will perform at most n + I 1 comparisons.

5. Hence on any input with I inversions, the running time of Insertion Sort is lower bounded by (I) and upper bounded by O(nI + 1). Show that if each element in the input array is at most k positions away from its final position in the sorted array then the number of inversions is O(nk), thereby implying that Insertion Sort will run in O(nk) time on such an array. If you need to you can assume that all the elements in the array are distinct.