How does the `key` arg in Python bisect work?

Question

I believe I understand sorting and bisection. When using key with sorted I get the results I expect, but when I call bisect(..., key=fn) I don't understand the outcome. Possibly a bug? Where would I report that?

from bisect import bisect

fn = lambda tup: (tup[0], tup[1] % 2, tup[1])

lst = [('a', 2), ('a', 1), ('a', 5), ('b', 3)]
x = ('a', 3)

print(sorted(lst, key=fn))        # [('a', 2), ('a', 1), ('a', 5), ('b', 3)]
print(sorted(lst + [x], key=fn))  # [('a', 2), ('a', 1), ('a', 3), ('a', 5), ('b', 3)]
# so `x` sorts into position 2.

lst.sort(key=fn)
print(bisect(lst, x, key=fn))     # 3 (!)

lst_fn = sorted([fn(item) for item in lst])
print(bisect(lst_fn, fn(x)))      # 2

I don't understand why x would sort to position 3. Am I missing something entirely?

Answer 1

bisect expects the lookup value x to already have key applied. So this works:

print(bisect(lst, fn(x), key=fn))  # 2

I think this is very counter-intuitive. After all, we're looking for a place to insert x, not fn(x).

Answer 2

https://github.com/python/cpython/issues/91966

The issue has been reported. Hopefully, the documentation will be updated soon.