title: For which cases following algorithm for counting inversions using merge sort will fail
body: <p>I have written the following code to count the number of inversions in an array of numbers.It gives correct results for the inputs that i tested it for but still it fails the test cases,I don't have access to test cases an i am not able to figure out for which cases it will fail,I can really use some help here.</p>
  
  <pre class="lang-py prettyprint-override"><code> def count_inversion(array):
          """
          counts number of inversions in array using divide and conquer
          an inversion is a pair (x,y) such that x &gt; y, example in array
          [3,1,2] there are two inversions (3,1), (3,2)
          """
          length = len(array)
          if length == 1 or length == 0:
              return array,0
          elif length == 2:
              if array[0] &gt; array[1]:
                  array.sort()
                  return array,1
              else:
                  return array,0
          else:
              left_array,left_count = count_inversion(array[:length/2])
              right_array,right_count = count_inversion(array[length/2:])
              across_arr,across_count = count_split(left_array,right_array)
              return across_arr,left_count + right_count + across_count
  
  def count_split(left,right):
      """
      counts the number of inversions across split pair
      left and right, by piggy backing on merge routine 
      of merge sort
      """
      l = 0 
      r = 0
      merge = []
      count = 0
      inversions = 0
      last_r = 0
      try:
          while True:
              if left[l] &gt; right[r]:
                  merge.append(right[r])
                  if r == 0 or r == last_r:
                      inversions = 0
                  inversions += 1
                  r = r + 1
              else:
                  merge.append(left[l])
                  count = count + inversions
                  l = l + 1
                  last_r = r
  
      except IndexError:
          if r == len(right):
              while l &lt; len(left):
                  count += inversions
                  merge.append(left[l])
                  l = l + 1 
          else:
              while r &lt; len(right):
                  merge.append(right[r])
                  r = r + 1
      return merge,count
  
  if __name__ == '__main__':
      f = open('inversions.txt')
      arr = []
      for line in f:
          arr.append(int(line))
      # arr is a list of integers which are not sorted in any sense
      # we are required to count number of inversions in arr
      print count_inversion(arr)[1]
  </code></pre>