Python :在没有多个函数调用的情况下计数inversion

Question

我试图计算在Python中实现mergesort算法时发生的反转次数，它只使用一个简单的函数定义(即mergesort的一个def语句)。为了清晰起见，我对这种合并算法进行了评论：

import csv

def safeint(val):
   try:
      return int(val)
   except ValueError:
      return val

list = []
with open('file.txt') as f:
    lines = csv.reader(f, delimiter='\n')
    for line in lines:
        line = map(safeint, line)
        list.append(line)

def mergesort(list):
    mid = len(list)//2  #MIDPOINT FOR DIVISION
    lft, rgt = list[:mid], list[mid:]
    if len(lft) > 1: lft = mergesort(lft)   #SORT BY HALVES
    if len(rgt) > 1: rgt = mergesort(rgt)
    res = []
    while lft and rgt:  #NEITHER HALF IS EMPTY
        if lft[-1] >=rgt[-1]:   #lft HAS GREATEST LAST VALUE
            res.append(lft.pop())   #APPEND IT
        else:   #rgt HAS GREATEST LAST VALUE
            res.append(rgt.pop())   #APPEND IT
    res.reverse()   #RESULT IS BACKWARD
    return (lft or rgt) + res   #ALSO ADD THE REMAINDER

print mergesort(list)

我的输入( file.txt )的形式如下：

1
2
3
4
5
55
60
82
19

我的输出是(如预期的)：

[[1], [2], [3], [4], [5], [19], [55], [60], [82]]

是否有可能在不添加额外的def语句的情况下将“逆计算器”合并到此代码中？网上已经有很多多功能的例子，例如：Counting Inversions Using Merge Sort，https://codereview.stackexchange.com/questions/12922/inversion-count-using-merge-sort

我们能说得更简洁点吗？

Answer 1

Python-ish伪代码：

while lft and rgt:  #NEITHER HALF IS EMPTY
    if lft[-1] >=rgt[-1]:   #lft HAS GREATEST LAST VALUE
        # if the last of lft is greater than the last of rgt (which is sorted),
        # then it is also greater than everything before the last element of rgt, 
        # so it generates as many inversions as the remaining elements in rgt
        inversions += len(rgt)
        res.append(lft.pop())   #APPEND IT
    else:   #rgt HAS GREATEST LAST VALUE
        res.append(rgt.pop())   #APPEND IT

如果inversions是全局的，则是一个参数(例如，使它成为一个1元素列表，因此它是可变的)或您返回的东西(在这种情况下，请确保返回两部分的反转之和)。