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?
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).