Merge sort to count split inversions in Python

Question

I am trying to use mergesort--which I get--to count the number of split inversions in a list (that is, where an element in the first half of the unsorted list should appear after a given element in the second half of the unsorted list; for example [3 2 1 4] would contain the split inversion (3, 1), but not (3, 2) as 3 and 2 are both in the first half). When I get to the final print statement, I am getting the answer I expect--in this case 9--but the return value is all wonky since it's returning the split value through the recursion. I've tried all sorts of combinations of indexing to no avail. Any help? (using Python 2.7)

(For the record, this is a Coursera homework problem, but I'm just learning for fun--no one's grading this other than me.)

def mergesort(lst):
    '''Recursively divides list in halves to be sorted'''
    if len(lst) is 1:
        return lst
    middle = int(len(lst)/2)
    left  = mergesort(lst[:middle])
    right = mergesort(lst[middle:])
    sortedlist = merge(left, right)
    return sortedlist

def merge(left, right):
    '''Subroutine of mergesort to sort split lists.  Also returns number
    of split inversions (i.e., each occurence of a number from the sorted second
    half of the list appearing before a number from the sorted first half)'''
    i, j = 0, 0
    splits = 0
    result = []
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
            splits += len(left[i:])
    result += left[i:]
    result += right[j:]
    print result, splits
    return result, splits


print mergesort([7,2,6,4,5,1,3,8])

Answer 1

Modify your mergesort function to disregard the intermediate splits.

def mergesort(lst):
    '''Recursively divides list in halves to be sorted'''
    if len(lst) == 1:
        return lst, 0
    middle = len(lst)/2
    left = mergesort(lst[:middle])[0]  # Ignore intermediate splits
    right = mergesort(lst[middle:])[0]  # Ignore intermediate splits
    sortedlist, splits = merge(left, right)
    return sortedlist, splits