Coutning inversions - python

inversions.py

## mergesort
def inversions(arr):
    (array, inv) = count_inversions(arr)
    return inv

def count_inversions(arr):
  if len(arr) <= 1:
    return (arr, 0)
  mid = len(arr) / 2
  left  = arr[:mid]
  right = arr[mid:]
  (left,  x) = count_inversions(left)
  (right, y) = count_inversions(right)
  (whole, z) = count_split(left, right)
  return (whole, x + y + z)

def count_split(s, t):
  res = []
  i = 0
  j = 0
  inversions = 0
  while(i < len(s) and j < len(t)):
    if s[i] <= t[j]:
      res.append(s[i])
      i += 1
    else:
      inversions += len(s[i:])
      res.append(t[j])
      j += 1
  if j < len(t):
    res += t[j:]
  if i < len(s):
    res += s[i:]
  return (res, inversions)

def main():
  arr = []
  with open('IntegerArray.txt') as openfileobject:
    for line in openfileobject:
        arr.append(int(line))
  print inversions(arr)

main()