When will the following inversion counting algorithm using merge sort fail

I wrote the following code to count the number of inversions in an array of numbers. It gives correct results for the input I tested, but still it failed the test cases, I don't have access to the test cases I can't figure out in what cases it will fail, I can really use some help here.

 def count_inversion(array):
        """
        counts number of inversions in array using divide and conquer
        an inversion is a pair (x,y) such that x > 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] > 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] > 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 < len(left):
                count += inversions
                merge.append(left[l])
                l = l + 1 
        else:
            while r < 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]

      

+3


source to share


1 answer


Try

3 4 6 1 2 5

      



Your answer is 5. The
real answer is 7.

It smells like homework / online judge, so I will say that your error is somewhere in the exception block.

+3


source







All Articles