gistfile1.py

import sys
import os

def inversions_and_sort(input_array):
  output = [] 
  inversions = 0 
  left = []
  right = []
  right_inversions = []
  left_inversions = []
  if len(input_array) > 1:
    left, left_inversions = inversions_and_sort(input_array[:len(input_array)/2])
    right, right_inversions = inversions_and_sort(input_array[len(input_array)/2:]) 
  else:
    return input_array, inversions

  inversions = left_inversions + right_inversions
  while len(left) or len(right):
    if len(left) and len(right):
      if left[0] <= right[0]:
        output.append(left[0])
        left = left[1:]
      else:
        output.append(right[0])

        for k in range(len(left)):
          inversions += 1

        right = right[1:]
    elif len(left):
      output.append(left[0])
      left = left[1:]
    elif len(right):
      output.append(right[0])
      right = right[1:]

  return (output, inversions)

def main():
  input_array = [int(i.strip()) for i in open('IntegerArray.txt').readlines()] 
  output, inversions = inversions_and_sort(input_array)
  print inversions

if __name__ == '__main__':
  main()