Add `keylist` argument to `list.sort`

[dg-pb]

Feature or enhancement

Proposal:

def sorted(iterable, /, *, key=None, keylist=None, reverse=False):
    ...

keylist is an extension that allows providing keys to list.sort that will be used for sorting.
This allows bypassing key generation via callable key argument or using zip with itemgetter in situations where possible.
The above are all relatively expensive operations, thus performance gain is non-trivial.

keylist accepts list, which will be mutated as part of sorting.
To prevent mutation of the input (or to supply arbitrary iterable), make a copy:

a.sort(keylist=list(my_keys))

List of examples and benchmarks is present in discourse thread.

TLDR: These are 3 main takeaways:

1. Faster argsort without needing to use dunder method

# Current one best way
indices = sorted(range(N), key=seq.__getitem__)    # 32 ms (100K ints)
# After this:
indices = sorted(range(N), keylist=list(seq))      # 26 ms (100K ints)

2. Non-trivial performance for dict sorting (or any other problem that is of the same nature)

Performance improvement against current alternative is 2-5x.

keys = list(d)
values = list(d.values())
values.sort(keylist=keys)

3. Generally better performance whenever keylist is ready or faster ways to construct it are available

values = list(range(100_000))
%timeit list(map(lambda x: x % 10, l))  # 7.71 ms (What happens via `key`)
%timeit [x % 10 for x in l]             # 3.23 ms (If could be done manually)

---

In short, it provides an entry into list.sort function that makes it possible to take faster path in many cases where input list is not the same as sort keys.

Has this already been discussed elsewhere?

I have already discussed this feature proposal on Discourse

Links to previous discussion of this feature:

https://discuss.python.org/t/allow-sorted-to-take-list-for-key-argument/105106

Linked PRs

• gh-142105: Add keylist argument to list.sort #142106

[picnixz]

FTR, I'm not sure we can actually change built-ins without a PEP. Irit told me that it wasn't possible to do so when we wanted to add some methods to ExceptionGroup but PEP-618 is an example where adding a new keyword to a built-in required a PEP.

[picnixz]

Actually, considering the DPO post has not yet gathered concrete support and that I think we really need a PEP, I'm going to close this issue and corresponding PR. In addition, I would advise to create branches on your own fork and share the implementation instead of opening a PR that would be sitting for some time (if a PEP had been submitted it may have been a bit more fine, but the process is still not finished).