Count Inversions in an Array

Given an array of n integers, count the number of inversions in it. A pair of indices (i, j) forms an inversion if i < j but arr[i] > arr[j]. An array that is already sorted in non-decreasing order has zero inversions, while one sorted in strictly decreasing order has the maximum possible number.

Input: The first line contains an integer n. The second line contains n space-separated integers. Output: Print a single integer: the total number of inversions in the array.

1 <= n <= 8000 -10^9 <= arr[i] <= 10^9

This is a beautiful example of getting a seemingly unrelated computation (inversion counting) essentially 'for free' by piggybacking on an existing algorithm's (merge sort's) own structure - a valuable pattern-recognition skill for augmenting known algorithms.

Count how many pairs of positions in an array are 'out of order' relative to each other. Brute force: Check every possible pair of indices directly, counting how many satisfy i<j but arr[i]>arr[j] - this costs O(n²), too slow for large arrays. Optimised: Piggybacking the inversion count onto merge sort's own merge step works because, when merging two ALREADY-SORTED halves, taking an element from the right half before the left is exhausted DIRECTLY tells you exactly how many left-half elements it's inverted with (all the ones still remaining) - counting this at every level of the recursion accumulates the TOTAL inversion count in the same O(n log n) time merge sort already takes.

1. Use a MERGE-SORT-based approach: recursively split the array in half and count inversions within each half separately, then count inversions BETWEEN the two halves during the merge step. 2. While merging two already-sorted halves, every time you take an element from the RIGHT half BEFORE the left half is exhausted, it forms an inversion with EVERY element still remaining in the left half. 3. Accumulate this count across every merge step of the recursion, using a 64-bit integer since the total can be large.

Time: O(n log n) - the same complexity as merge sort itself, since inversion counting is folded directly into the existing merge step. Space: O(n), for the temporary arrays used during merging.

The array could already be sorted (answer 0), or it could be sorted in strictly decreasing order (the maximum possible number of inversions, n*(n-1)/2).

Be ready to explain PRECISELY why taking from the right half early counts inversions with the ENTIRE remaining left half at once (not just one element) - this is the single insight that makes the O(n log n) approach work instead of needing O(n²).