optimal_sort_by_compares.py

import itertools


def make_sort(n):
    perms = tuple(itertools.permutations(range(n)))
    m = len(perms)
    cmp = tuple(tuple(sum(
        2 ** k for k in range(m) if perms[k][i] < perms[k][j]) for i in range(j)) for j in range(n))

    def f(mask):
        if not (mask & (mask - 1)):
            return 0
        b, b_lhs, b_rhs, = 0, None, None
        for i_cmp in cmp:
            for j_cmp in i_cmp:
                lhs, rhs = mask & j_cmp, mask & ~j_cmp
                if b < (s := min(lhs.bit_count(), rhs.bit_count())):
                    b, b_lhs, b_rhs = s, lhs, rhs
        return f(b_lhs) + f(b_rhs) + mask.bit_count()

    return f(2**m - 1) / m


if __name__ == '__main__':
    print([
        make_sort(n=n)
        for n in range(2, 9)
    ])