How does Counting Inversions work in the following code?

-synx-'s blog

By -synx-, history, 9 years ago, In English

a = 0
while max(V) > 0:
    C = [ 0 ] * max(V)
    for x in V:
        if x%2==0:
            a += C[x//2]
        else:
            C[x//2] += 1
    V = [ x//2 for x in V ]
print(a)

-synx-
9 years ago
2

Comments (1)

Show archived | Write comment?

rajat1603

9 years ago, hide # |

← Rev. 2 →

+12

Consider 2 numbers $\text{[math]}$ and $\text{[math]}$ . Write them down in binary (Assume both of them to be $\text{[math]}$ digit binary number (Incase their length is unequal , pad leading zeroes to the shorter one).

$\text{[math]}$
$\text{[math]}$

Let $\text{[math]}$ be the minimum index such that $\text{[math]}$

So $\text{[math]}$ is an inversion pair if and only if index of $\text{[math]}$ $\text{[math]}$ index of $\text{[math]}$ and $\text{[math]}$
So for any $\text{[math]}$ , $\text{[math]}$ and $\text{[math]}$ and $\text{[math]}$ and after that they are both equal so each pair gets counted towards as an inversion exactly once.