Recall that the worst number of inversions occur in an array sorted in descending order, in which each of the n elements is inverted with the other n – 1 elements. Why then, is the maximum number of inversions n( n – 1 ) / 2 instead of n( n – 1 )?

Question

```
1 for each j, from 1 to the length of A – 1
2 temp = A[ j ]
3 i = j – 1
4 while i is greater than -1 and A[ i ] is greater than temp
5 A[ i + 1 ] = A[ i ]
6 i—
7 A[ i + 1] = temp
```
A. There is only a 50% chance that each inversion will occur.
B. Since we are only sorting half the array, on average, we divide by 2 to compensate.
C. We are counting each inversion twice, so we must divide by 2.
D. Since we only need to swap the element at a front position of the array with the element in the corresponding back position of the array, one swap puts 2
elements in their proper positions, and so we divide by 2

Answer 1

C