1. Given an integer array A, A[i] and A[j] are inverted if i < j, but...

 

Transcribed Image Text:

1. Given an integer array A, A[i] and A[j] are inverted if i < j, but A[i]> A[j]. Consider the following array with 10 elements. In it, 1 < 2 but (A[1] = 5)> (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. 0 1 2 34 5 6 7 8 9 1 5 4 9 8 2 3 6 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. 1. Given an integer array A, A[i] and A[j] are inverted if i < j, but A[i]> A[j]. Consider the following array with 10 elements. In it, 1 < 2 but (A[1] = 5)> (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. 0 1 2 34 5 6 7 8 9 1 5 4 9 8 2 3 6 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.