In [10]:

    

f = open("IntegerArray.txt", "r")
source = [int(line) for line in f]
f.close()


    

    




100000

In [8]:

    

class Solution:
    def countInversions(self, arr):
        return self.doSort(arr, 0, len(arr)-1)

    def doSort(self, arr, p, q):
        if p == q:
            return 0
        k = (p+q)//2
        return self.doSort(arr, p, k) + self.doSort(arr, k+1, q) + self.doMerge(arr, p, k, q)

    def doMerge(self, arr, p, k, q):
        counter = 0
        n = q-p+1
        x = n*[None]
        s = p
        t = k+1
        for i in xrange(n):
            if s > k:
                x[i] = arr[t]
                t += 1
            elif t > q:
                x[i] = arr[s]
                s += 1
            else:
                if arr[s] <= arr[t]:
                    x[i] = arr[s]
                    s += 1
                else:
                    x[i] = arr[t]
                    counter += k-s+1
                    t += 1
        for i in xrange(n):
            arr[p] = x[i]
            p += 1
        return counter


    

In [9]:

    

print Solution().countInversions(source)


    

    




2407905288

In [ ]: