**2-4 Inversions**

Let

**of**

*inversion*- List the five inversions of the array
⟨2,3,8,6,1⟩ . - What array with elements from the set
1,2,…,n has the most inversions? How many does it have? - What is the relationship between the running time of insertion sort and the number of inversions in the input array? Justify your answer.
- Give an algorithm that determines the number of inversions in any permutation on
n elements inΘ(nlgn) worst-case time. (*Hint:*Modify merge sort.)

**1. List of Inversions**

Inversions in the given array are: (1, 5), (2, 5), (3, 4), (3, 5), and (4, 5). (

*Note:*Inversions are specified by indices of the array, not by values.)

**2. Array With Most Inversions**

The array with elements from the set

with the most inversions will have the elements in reverse sorted order, i.e.

As the array has

**3. Relationship With Insertion Sort**

If we take look at the pseudocode for insertion sort with the definition of inversions in mind, we will realize that the more the number of inversions in an array, the more times the inner

**while**loop will run. The reason being more inversions means most of the array is reverse sorted, i.e. more swaps to perform in the while loop.

So, the higher the number of inversions in an array, the longer insertion sort will take to sort the array.

**4. Algorithm to Calculate Inversions**

Although a hint to modify merge sort is already given, without that also we should think of divide-and-conquer algorithms whenever we see running time of

As was done in merge sort, we need to recursively divide the array into halfs and count number of inversions in the sub-arrays. This will result in

steps and

def merge(items, p, q, r): L = items[p:q+1] R = items[q+1:r+1] i = j = 0 k = p inversions = 0 while i < len(L) and j < len(R): if(L[i] < R[j]): items[k] = L[i] i += 1 else: items[k] = R[j] j += 1 inversions += (len(L) - i) k += 1 if(j == len(R)): items[k:r+1] = L[i:] return inversions def mergesort(items, p, r): inversions = 0 if(p < r): q = (p+r)/2 inversions += mergesort(items, p, q) inversions += mergesort(items, q+1, r) inversions += merge(items, p, q, r) return inversions items = [4,3,2,1,17] inversions = mergesort(items, 0, len(items)-1) print items,inversions