New Results for Adaptive and Approximate Counting of Inversions

Saladi Rahul

Counting inversions is a classic and important problem in databases. The number of inversions, $K^{\ast }$, in a list $L=(L(1),L(2),\dots ,L(n))$ is defined as the number of pairs $i < j…