Count the inversions in the array 5, 4, 1, 3, 2. Give the number and describe the O(n log n) algorithm along with the exact place in it where the count is accumulated.

Count the inversions in the array 5, 4, 1, 3, 2. Give the number and describe the O(n log n) algorithm along with the exact place in it where the count is accumulated.

Approach: Count inversions inside each half recursively, then count the cross pairs while merging, using the fact that both halves are sorted at that moment.

8. Directly, 5 beats 4, 1, 3 and 2 for four inversions, 4 beats 1, 3 and 2 for three, 3 beats 2 for one, and 1 beats nothing, giving 4 + 3 + 1 = 8. The O(n log n) algorithm is divide and conquer, merge sort with a counter. Split, recurse on both halves, then merge. When the merge takes an element from the right half while k elements remain unconsumed in the left half, every one of those k left elements is greater than the taken element and appears before it, so add k to the count at that moment. Each level of the recursion does O(n) merge work and there are log n levels, giving O(n log n) total, and the recurrence T(n) = 2T(n/2) + O(n) is the master theorem case with equal work per level. A Fenwick tree over compressed values gives the same bound by scanning right to left and querying the count of values already inserted that are smaller than the current one.

Follow-up: How would you count pairs with a[i] > 2 * a[j] for i < j in the same time bound?

Key concepts: merge sort, cross inversions, divide and conquer, fenwick tree.