python list being interpreted as an integer; counting inversions

Question

Getting error:

File "inversions.py", line 26, in merge
if left[i] < right[j]:
TypeError: 'int' object is not subscriptable

My implementation of merge sort is like so; accepts a list and it's length. Base case is when length is 1, where I simply return the list (not as an int, but as a list):

def mergesort(arr, length):
    if length == 1:
        return arr

Working of merge sort function in non-base-case situation:

    n = length // 2
    left = arr[:n]
    right = arr[n:]

    lsort = mergesort(left, len(left))
    rsort = mergesort(right, len(right))
    result = merge(lsort, rsort, length)

    return result

Then there's the merge function for merging two sorted sub-lists, defined like so:

def merge(left, right, length):
    buff = []
    i = j = count = 0

This merge function is obviously called by the merge sort function after all recursive calls are done.

There are if-else statements in this merge function that handle it's working:

    if left[i] < right[j]:
        buff.append(left[i])
        i += 1

        if i == len(left):
            for j in range(j, len(right)):
                buff.append(right[j])
            break

    elif left[i] > right[j]:
        buff.append(right[j])
        j += 1

        count += len(left) - i

        if j == len(right):
            for i in range(i, len(left)):
                buff.append(left[i])
            break

In the end, this merge function returns 'count'; number of inversions.

Judging from the error, it seems that 'left' etc are being interpreted as integers, thus giving me the subscript error. But I just can't understand WHY they are ints when clearly they should be lists (or maybe I'm just missing something very obvious).

I just can't get my head around this. Any and all help is appreciated! :)

Answer 1

I've seen your code, and in merge function you're returning the variable count of type int and then passing it to merge again as array in the recursion. So the block if left[i] < right[j]: won't work.

Change merge function to return buff variable.