Given an integer array A, A[i] and A[j] are inverted if i A[j]. Consider the following array with 10 elements. In it, 1 (A[2] = 4), so 5-4 is an inversion. In this array there are a total of 15 inversions: 4-2, 4-3, 5-2, 5-3, 5-4, 8-2, 8-3, 8-6, 8-7, 9-2, 9-3, 9- 6, 9-7, 9-8, and 10-7

1. Given an integer array A, Alil and Alil are inverted if iAli. Consider the following array with 10 elements. In it, 1(A2 4), so 5-4 is an inversion. In this array there are a total of 15 inversions: 4-2, 4-3, 5-2, 5-3, 5-4, 8-2, 8-3, 8-6, 8-7, 9-2,9-3, 9- 6, 9-7,9-8, and 10-7. 15 498 2 36 10 7 (a) [3 pts] Write a divide-and-conquer algorithm to count the number of inversions in an integer array A of size n (b) [2 pts] Set up a recurrence relation for the run time of your algorithm in the worst case. Briefly explain how each term in the recurrence arises. Solve the recurrence using the Master Method