CODEWITHSUNDEEP
pythonsortingmergecountinversion
RRock
RRock

Reputation: 11

inversion count using merge sort python

I'm implementing a merge sort with inversion count. my code works fine with my small input file (10 elements) but when it goes to 100000, it seems return incorrect answer from brute search. sometimes bigger and sometimes smaller. someone has any idea?

my code returns 2402298631. input file location http://spark-public.s3.amazonaws.com/algo1/programming_prob/IntegerArray.txt

def msort_inv2(m):

    global count

    if len(m) <= 1:
        return m
    result = []
    middle = int(len(m)/2)

    left = msort_inv2(m[:middle])
    right = msort_inv2(m[middle:])

    while (len(left) > 0) or (len(right) > 0):
        if (len(left) > 0) and (len(right) > 0):
            if left[0] > right[0]:
                result.append(right[0])
                count = count + len(left)
                right.pop(0)
            else:
                result.append(left[0])
                left.pop(0)
        elif len(right) > 0:
            for i in right:
                result.append(i)
                right.pop(0)
        else:
            for i in left:
                result.append(i)
                left.pop(0)
    return result

Upvotes: 0

Views: 1067

Answers (1)

RRock
RRock

Reputation: 11

the bug exists in following portion

    elif len(right) > 0:
        for i in right:     # bug !!!!
            result.append(i)
            right.pop(0)
    else:
        for i in left:
            result.append(i)
            left.pop(0)

the correction would be like this

    elif len(right) > 0:
        result.extend(right)
        right = []
    else:
        result.extend(left)
        left = []

for loop in an array and pop out item at the same time, will cause weird behavior in python.

Upvotes: 1

Related Questions