Counting Inversions via Modified Merge Sort

Reported in interviews at Citadel Flow Traders

Problem statement

Given an array $A$ of $n$ integers, an inversion is a pair of indices $(i, j)$ with $i < j$ and $A[i] > A[j]$. Return the total number of inversions.

Constraints:

  • $1 \leq n \leq 10^6$
  • $-10^9 \leq A[i] \leq 10^9$
  • Elements may repeat
  • The inversion count can exceed $2^{31} - 1$, so use a 64-bit integer for the count
  • Target: $O(n \log n)$ time, $O(n)$ space

Example 1:

  • Input: A = [2, 4, 1, 3, 5]
  • Output: 3
  • Explanation: The inversions are $(2,1)$, $(4,1)$, $(4,3)$.

Example 2:

  • Input: A = [5, 4, 3, 2, 1]
  • Output: 10
  • Explanation: Every pair is an inversion. $\binom{5}{2} = 10$.

Example 3:

  • Input: A = [1, 1, 1]
  • Output: 0
  • Explanation: Equal elements do not form inversions (strict inequality required).
Show hint

If you split the array in two, which pairs can recursion count for you and which ones need extra work?

Relevant roles: ML Engineer, AI Engineer, Forward Deployed Engineer and LLM Engineer.

Related free problems