Count Inversions

Problem

Count the pairs (i, j) with i < j and arr[i] > arr[j].

Adapt merge sort: whenever an element from the right half is taken during a merge, all remaining left elements form inversions with it. Equal elements never count.

Hint

Taking from the right half means every left element still unmerged is strictly larger.

Test cases

case 1

in: [[2,4,1,3,5]]

expected: 3

case 2

in: [[5,4,3,2,1]]

expected: 10

case 3

in: [[1,2,3]]

expected: 0

case 4

in: [[]]

expected: 0

case 5

in: [[2,2,2]]

expected: 0

Starter codePython

def count_inversions(arr):
    # Your code here
    pass

5 test cases · run your code against them in the editor