40 lines
937 B
Python
40 lines
937 B
Python
def _inversions(xs):
|
|
# Can't be unsorted
|
|
if len(xs) < 2: return 0, xs
|
|
|
|
# Divide into two subarrays
|
|
leng = len(xs)//2
|
|
left = xs[:leng]
|
|
right = xs[leng:]
|
|
|
|
# Perform recursive call
|
|
lcount, left = _inversions(left)
|
|
rcount, right = _inversions(right)
|
|
|
|
# Reverse the lists to allow O(1) pop.
|
|
# Since we already have an O(n) copy,
|
|
# this doesn't increase complexity.
|
|
left.reverse()
|
|
right.reverse()
|
|
|
|
# Merge by popping
|
|
count = 0
|
|
total = []
|
|
while left != [] and right != []:
|
|
if left[-1] <= right[-1]:
|
|
total.append(left.pop())
|
|
else:
|
|
total.append(right.pop())
|
|
count += len(left)
|
|
|
|
# Add elements from non-empty array,
|
|
# if applicable.
|
|
left.reverse()
|
|
right.reverse()
|
|
total += left + right
|
|
return (count + lcount + rcount), total
|
|
|
|
def num_inversions(xs):
|
|
count, _ = _inversions(xs)
|
|
return count
|