Simple inversions count in an array in Python (for Algorithms: Design and Analysis, Part 1 on Coursera)

inversions_count.py

#!/usr/bin/python

def count_inversions(arr, length):
	if length == 1:
		return (arr,0)
	else:
		left = arr[:length/2]
		right = arr[length/2:]
		(a,x) = count_inversions(left, len(left))
		(b,y) = count_inversions(right, len(right))
		(c,z) = merge_and_countsplitinv(a, b, length)
		return (c,x+y+z)

def merge_and_countsplitinv(left, right, length):
	count_inv = 0
	i = j = 0
	out = [None] * length
	right_len = len(right)
	left_len = len(left)
	for k in range(length):
		if j >= right_len or (i < left_len and left[i] < right[j]):
			out[k] = left[i]
			i += 1
		else:
			out[k] = right[j]
			count_inv += (left_len - i) 
			j += 1
	return (out,count_inv)

if (__name__ == '__main__'):
	arr = [9, 2, 1, 5, 2, 3, 5, 1, 2, 32, 12, 11]
	print count_inversions(arr, len(arr))[1]