两种排序的最坏比较次数

把五个元素的全部 120 种排列都跑一遍，插入排序和归并排序各自最坏比了多少次：

import math
from itertools import permutations

def merge_cmp(a):
    """归并排序，返回比较次数"""
    c = 0
    def go(x):
        nonlocal c
        if len(x) <= 1:
            return x
        m = len(x) // 2
        L, Rr = go(x[:m]), go(x[m:])
        out, i, j = [], 0, 0
        while i < len(L) and j < len(Rr):
            c += 1
            if L[i] <= Rr[j]:
                out.append(L[i]); i += 1
            else:
                out.append(Rr[j]); j += 1
        return out + L[i:] + Rr[j:]
    go(list(a))
    return c

def ins_cmp(a):
    """插入排序，返回比较次数"""
    a = list(a); c = 0
    for i in range(1, len(a)):
        j, x = i - 1, a[i]
        while j >= 0:
            c += 1
            if a[j] <= x:
                break
            a[j + 1] = a[j]; j -= 1
        a[j + 1] = x
    return c

P = list(permutations(range(5)))
print(str(max(ins_cmp(p) for p in P)) + "/" + str(max(merge_cmp(p) for p in P)))