合并排序以计算Python中的拆分反转

Question

我试图使用mergesort - 我得到 - 来计算列表中的拆分反转次数(也就是说,未排序列表的前半部分中的元素应该出现在后半部分中的给定元素之后)未排序的列表;例如[3 2 1 4]将包含拆分反转(3,1),但不包含(3,2),因为3和2都在前半部分).当我得到最终的打印语句时,我得到了我期望的答案 - 在这种情况下为9 - 但返回值都是因为它通过递归返回拆分值而变得很难.我已经尝试了各种索引组合无济于事.有帮助吗？(使用Python 2.7)

(为了记录,这是一个Coursera的家庭作业问题,但我只是为了好玩而学习 - 除了我以外,没有人对此进行评分.)

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])