Coursera Algo-005 Programming Question 1

merge_sort_inversions.py

"""
Use merge sort to count inversions.
"""

with open('IntegerArray.txt') as f:
  ints = [int(line) for line in f.readlines()]

#print 'First 5 ints:{}'.format(ints[:5:])

inversions = 0

def sort_array(array, is_recursion=False, level=1):
  """
  Merge sort implementation.
  Recursively sort.
  TODO: Handle non-uniqueness.
  """
  # Handle base case.
  if len(array) == 1: return array
  # Divide, recurse, and merge.
  a, b = divide_array(array)
  a = sort_array(a, True, level + 1)
  b = sort_array(b, True, level + 1)
  #print 'level {}: a: {}, b: {}'.format(level, a, b)
  return merge_arrays(a, b)

def divide_array(array):
  """
  Split in two.
  """
  l = len(array) / 2
  a = array[:l:]
  b = array[l::]
  return a, b

def merge_arrays(a, b):
  """
  Zip back together sorted arrays.
  """
  global inversions
  array = []
  l = len(a) + len(b)
  i_a = 0
  i_b = 0
  n = None
  for i in range(l):
    if i_a < len(a) and (i_b >= len(b) or a[i_a] < b[i_b]):
      n = a[i_a]
      if (i_a + 1) < len(a): i_a += 1
      else: i_a = len(a)
      #print 'a: {}'.format(n)
    else:
      n = b[i_b]
      # Had to look this up, but merge sort simplifies finding the inversion
      # count. It's just the remaining numbers to be added from the left sub-
      # array after inserting a number from the right.
      inversions += len(a) - i_a
      if (i_b + 1) < len(b):
        i_b += 1
      else: i_b = len(b)
      #print 'b: {}'.format(n)
    array.append(n)
  return array

#print merge_arrays([1,3,5], [2,4,6])

#test_ints = [1,3,5,2,4,6] # 3 inversions
#test_ints = [1,5,3,2,4] # 4 inversions
#test_ints = [5,4,3,2,1] # 10 inversions
#test_ints = [1,6,3,2,4,5] # 5 inversions
#test_ints = [9,12,3,1,6,8,2,5,14,13,11,7,10,4,0] # 56 inversions
#print 'unsorted: {}'.format(test_ints)
#print 'sorted: {}'.format(sort_array(test_ints))

sort_array(ints)

print 'inversions: {}'.format(inversions)

IntegerArray.txt not included due to its sheer length. Don't want to add something like that to the DOM.