Solution to Array-Inversion-Count by codility

inversions.py

# https://codility.com/demo/take-sample-test/array_inversion_count
import bisect

def solution(A):
    """ computes the number of inversions in A, or returns -1 if it exceeds 1,000,000,000
    """
    # the idea is to store elements left of n-th sorted,
    # which would allow us to easily find the number of them greater than n-th.
    sorted_left = []
    res = 0
    for i in xrange(1, len(A)):
        bisect.insort_left(sorted_left, A[i-1])
        # i is also the length of sorted_left
        res += (i - bisect.bisect(sorted_left, A[i]))
        if res > 1000000000:
            return -1
    return res

assert solution([1, 2]) == 0
assert solution([2, 1]) == 1
assert solution([-1, 6, 3, 4, 7, 4]) == 4
assert solution([]) == 0