Counting Inversions

Definition (Inversion)

Ranking 1 = $\{1,2,\dots ,n\}$ and Ranking 2 = $\{a_1,a_2,\dots ,a_n\}$. Elements $i$ and $j$ of $a$ are inverted if $i<j$ but $a_i>a_j$

Similarity Metric: The fewer inversions between two rankings, the more similar they are.

Goal: Count the number of inversions

Divide: Separate list into two halved $A$ and $B$ Conquer: Recursively count inversions in each list Combine: Count inversions $(a,b)$ with $a\in A$ and $b\in B$

• Sort $A$ and $B$
• For each element $b\in B$, binary search in $A$ to find how many elements in $A$ are greater than $b$