Краткий ответ

В sorted и list.sort функция параметра key вычисляется один раз для каждого элемента сортируемой последовательности, а затем сортировка сравнивает уже полученные ключи. Это избегает повторного дорогого вычисления признака при многочисленных сравнениях и обычно снижает время работы.

Исторический контекст

Такой подход решает типичную проблему сортировки объектов, когда критерий порядка нужно получать через вычисление: разбор строки, обращение к атрибутам, преобразование даты или вычисление составного признака. Если вычислять критерий заново при каждом сравнении, стоимость сортировки начинает зависеть не только от числа элементов, но и от числа сравнений.

Параметр key реализует распространённую схему «украсить — отсортировать — убрать украшение»: сначала для элементов получают ключи, затем сортируют пары «ключ и исходный элемент», после чего возвращают исходные элементы в новом порядке.

Постановка проблемы

Для n элементов сортировка обычно выполняет порядка n log n сравнений. Если вычисление ключа занимает заметное время, его повторный вызов при сравнениях может стать основным узким местом.

Однако предварительное вычисление ключей тоже требует дополнительной памяти — обычно порядка O(n) для временного хранения ключей. Поэтому при очень больших наборах данных нужно учитывать не только ускорение, но и пиковое потребление памяти.

Подробное решение

При использовании key Python вызывает функцию для каждого входного элемента один раз в рамках конкретной операции сортировки. Результаты сохраняются во внутренней структуре, а алгоритм сортировки сравнивает ключи, а не повторно вызывает функцию для исходных объектов.

items = [(3, 30), (1, 10), (2, 20)]
ordered = sorted(items, key=lambda item: item[1])
print(ordered)

Здесь выражение item[1] вычисляется по одному разу для каждого элемента. После этого сравниваются значения 30, 10 и 20, а результатом остаются исходные кортежи.

Это отличается от передачи функции сравнения через functools.cmp_to_key: функция сравнения может вызываться много раз, поскольку участвует непосредственно в отдельных сравнениях. Поэтому при наличии естественного вычисляемого ключа параметр key обычно предпочтительнее.

Ключ должен быть согласованным: если он возвращает значения, которые нельзя сравнивать между собой, сортировка завершится исключением. Также вычисление ключа может иметь побочные эффекты, но полагаться на конкретный порядок таких вызовов не следует.

Если один и тот же набор объектов сортируется многократно по одному критерию, ключи иногда выгодно вычислить и сохранить самостоятельно. Это уменьшает повторные вычисления между операциями, но увеличивает время жизни и память, занятые сохранёнными ключами.

Ситуация из практики

В сервисе сортировали большой список записей по нормализованному имени: функция удаляла лишние пробелы и приводила строку к единому регистру. Сначала нормализацию выполняли внутри логики сравнения, из-за чего дорогая операция повторялась множество раз.

Рассматривались два варианта. Ручное кэширование ключей давало контроль над временем жизни кэша, но усложняло код и требовало удалять устаревшие ключи. Передача функции через key была проще и ограничивала кэширование одной операцией сортировки, но добавляла временную память на ключи.

Выбрали key, потому что сортировка выполнялась пакетно, а ключи после неё не требовались. Количество нормализаций стало линейным относительно числа записей, а лишняя память освобождалась после завершения операции. Для потоковой обработки, где весь набор нельзя держать в памяти, вместо этого рассматривали предварительную нормализацию при загрузке или внешнюю сортировку.

Что кандидаты часто упускают

Вопрос: Вычисляется ли функция key один раз на элемент при каждой последующей сортировке того же списка?

Ответ: Нет, гарантия действует только внутри одной операции сортировки. При новом вызове sorted или list.sort ключи вычисляются заново, если приложение не сохранило их самостоятельно. Поэтому повторные сортировки по неизменившемуся критерию могут оправдать явное хранение ключей, но это уже отдельный компромисс по памяти и актуальности данных.
Вопрос: Почему параметр key не гарантирует отсутствие временного роста памяти?

Ответ: Для эффективного сравнения Python должен связать каждый исходный элемент с вычисленным ключом. Эти ключи и служебные структуры требуют дополнительной памяти, обычно линейной относительно размера сортируемой последовательности. После сортировки исходные элементы сохраняются, а ключи становятся ненужными и могут быть освобождены; поэтому важен именно пиковый, а не только конечный расход памяти.
Вопрос: Всегда ли функция key быстрее функции сравнения?

Ответ: Нет. Для простого критерия разница может быть небольшой, а создание сложных ключей способно само стать дорогим. Кроме того, функция сравнения иногда необходима, когда порядок нельзя выразить независимым сопоставимым ключом. Но если один и тот же критерий можно вычислить заранее для каждого элемента, key обычно масштабируется лучше, поскольку стоимость вычисления становится O(n), тогда как сравнение может выполняться порядка O(n log n) раз.