Divide and conquer algorithm for counting array inversions

counting_inversions.py

def sort_and_count(array):
  if len(array) <= 1:
    return 0, array

  mid = len(array) / 2

  left_array = array[0:mid]
  right_array = array[mid:len(array)]

  left_result = sort_and_count(left_array)
  right_result = sort_and_count(right_array)

  merge_result = merge_and_sort(left_result[1], right_result[1])

  return (left_result[0] + right_result[0] + merge_result[0]), merge_result[1]

def merge_and_sort(left_array, right_array):
  result = []
  i = 0
  j = 0
  k = 0
  inversions = 0

  l_len = len(left_array)
  r_len = len(right_array)


  while i < l_len and j < r_len:
    if left_array[i] < right_array[j]:
      result.append(left_array[i])
      i += 1
    else:
      result.append(right_array[j])
      j += 1
      inversions += (l_len - i)

  if i < l_len:
    result += left_array[i:l_len]
  else:
    result += right_array[j:r_len]

  return inversions, result

Looking over your code there's a small mistake on line 5
mid = len(array) # for odd number of elements mid will be a floating point number
Use floor division instead
mid = len(array) // 2

The rest is just fine : )