Python mergesort：在没有多次函数调用的情况下计算反转

Question

我正在尝试计算 Python 中合并排序算法的以下实现中发生的倒置次数，该算法仅使用一个简单的函数定义（即一个 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], [19], [55], [60], [82]]

是否可以在不添加额外的 def 语句的情况下将 "inversions calculator" 合并到此代码中？网上已经有很多多功能的例子，例如：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 元素列表，因此它是可变的）或您 return 的东西（确保 return在这种情况下，两半的反转总和）。

Python mergesort：在没有多次函数调用的情况下计算反转

Python mergesort: counting inversions without multiple function calls

python

algorithm

mergesort