Question 3: Given an unsorted array, an inversion is a pair of indices i, j so that i < j and A[i] > A[j]. For example a sorted array has no inversion. An array sorted in reverse has an inversion for any i < j. Give an algorithm that finds the number of inversions in an unsorted array.

Please answer with an explanation of the algorithm in words.