-synx-'s blog

How does Counting Inversions work in the following code?
By -synx-, history, 8 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)
  • Vote: I like it
  • +10
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
8 years ago, # |
← Rev. 2   Vote: I like it +12 Vote: I do not like it

Consider 2 numbers and . Write them down in binary (Assume both of them to be digit binary number (Incase their length is unequal , pad leading zeroes to the shorter one).



Let be the minimum index such that

So is an inversion pair if and only if index of index of and
So for any , and and and after that they are both equal so each pair gets counted towards as an inversion exactly once.

→ Reply