40 Counting Number of Inversions

Let $a_{1}, a_{2}, \dots, a_{n}$ be a given list/array of $n$ numbers.

Definition

Two numbers $a_{i}$ and $a_{j}$ form an inversion if $i < j$ but $a_{i} > a_{j}$

The number of inversions measures the “sortedness” of the array

Naive Algorithm: Needs $O (n^{2})$ time as it checks if each of the $(2 n)$ pairs is an inversion or not.

Inspired by MergeSort

Three steps for divide-and-conquer algorithm

Divide: Divide the list $L$ into two equal pieces, say $L_{1}$ and $L_{2}$
Conquer: Count the number of inversions within $L_{1}$ and $L_{2}$
Combine: Count the number of inversions where one number is from $L_{1}$ and other number is from $L_{2}$

Let $T (n)$ be time needed to count number of inversions from a given list of $n$ numbers

We do the following improvements

Divide: Divide the list $L$ into two equal pieces, say $L_{1}$ and $L_{2}$
Conquer: Sort and count the number of inversions within $L_{1}$ and $L_{2}$
Combine:
- We can assume that $L_{1}$ and $L_{2}$ both are sorted
- Count the number of inversions where one number is from $L_{1}$ and other number is from $L_{2}$

Let $T (n)$ be time needed to count number of inversions from a given list of $n$ numbers

We need $O (1)$ for the Divide step
We need $2 \cdot T (n /2)$ time for the Conquer step
It can be shown that the Combine step now needs only $O (n)$ time as both $L_{1}$ and $L_{2}$ are sorted
Recurrence is $T (n) \leq 2 \cdot T (n /2) + O (n)$
Same as that for MergeSort, and solves to $T (n) = O (n lo g n)$

1 : 2 : 3 : 4 : 5 : 6 : 7 : 8 : 9 : 10 : 11 : 12 : 13 : Algorithm Combine (L_{1}, L_{2}) The input is two sorted lists L_{1} and L_{2} of length n /2 each Let L_{1} = {b_{1} < b_{2} < \dots < b_{n /2}} \leftarrow sorted Let L_{2} = {c_{1} < c_{2} < \dots < c_{n /2}} \leftarrow sorted Initialize i = 1 and j = 1 Initialize count = 0 while i \neq = n /2 and j \neq = n /2 do if b_{i} > c_{j} then Increase j by 1 Increase count by (n /2) - i + 1 else Increase i by 1 end if end while return count

Wed design an algorithm Sort-and-Count(L) which takes as an input a list $L$ and outputs two things:

1 : 2 : 3 : 4 : Algorithm Sort-and-Count (L) Divide L into two lists L_{1} and L_{2} of equal sizes Let (r_{1}, L_{1}^{'}) = Sort-and-Count (L_{1}) Let (r_{2}, L_{2}^{'}) = Sort-and-Count (L_{2}) Let (co u n t, L^{'}) be the output of Combine (L_{1}^{'}, L_{2}^{'}) return co u n t + r_{1} + r_{2} return L^{'}