Count inversions in a permutation

Problem

Given an array a of length n that is a permutation of distinct integers (e.g., 1..n), define an inversion as a pair of indices (i, j) such that:

• 0 ≤ i < j < n, and
• a[i] > a[j].

Task

Write a function that returns the number of inversions in the array.

Input/Output

• Input: an integer array a with all distinct values
• Output: a single integer = the number of inversions

Notes

• Any time complexity is acceptable (e.g., an O(n^2) approach is fine), but you may also discuss faster approaches if you know them.

Count Inversions in an Array

Given a list of distinct integers, return the number of pairs i < j with a[i] > a[j].

Constraints

• All values are distinct.
• 0 <= len(a) <= 200000

Examples

Example 1

Input: ([1, 2, 3, 4],)
Output: 0

Explanation: Already sorted has no inversions.

Example 2

Input: ([4, 3, 2, 1],)
Output: 6

Explanation: Reverse sorted has every pair inverted.

Hints

1. A merge-sort count adds the number of remaining left elements when taking from the right.