В чем разница между функциями sort и sorted в Python?

Что проверяют

Знаете ли вы разницу между изменением на месте и созданием нового объекта и понимаете ли, что из этого следует для памяти и для кода вокруг. Следом часто спрашивают, как отсортировать по нескольким полям или почему a = a.sort() превращает список в None.

Как отвечать

• list.sort(): метод есть только у списков. Сортирует тот же объект на месте и возвращает None. Это сознательное решение: по возвращаемому значению сразу видно, что исходные данные изменились;
• sorted(iterable): встроенная функция, принимает любой итерируемый объект (кортеж, множество, генератор, словарь, строку) и всегда возвращает новый список. Исходный объект не трогает;
• общие параметры: key и reverse, оба только именованные. key вызывается ровно один раз на элемент, поэтому key=str.lower или key=operator.itemgetter(1) дешевле, чем кажется. Параметра cmp в Python 3 нет, старый компаратор оборачивают в functools.cmp_to_key.

Под капотом у обоих один алгоритм, Timsort: O(n log n) в общем случае и линейное время на уже упорядоченных данных. Сортировка стабильная, элементы с равным ключом сохраняют исходный порядок. На этом держится сортировка по нескольким полям в два прохода: сначала по второстепенному ключу, потом по главному. Хотя обычно проще вернуть кортеж: key=lambda u: (u.city, -u.age).

По памяти: sorted сначала копирует данные в новый список, так что на миллионе элементов вы держите две копии ссылок. sort экономнее, хотя и ему нужен временный буфер для слияния. Правило простое: нужен исходный порядок или на входе не список, берите sorted; список ваш и в прежнем виде больше не нужен, берите sort.

Где спотыкаются

Пишут result = items.sort() и потом удивляются None. Или вызывают sort у кортежа и получают AttributeError.

Забывают, что sorted(d) по словарю вернёт отсортированные ключи, а не пары. Для пар нужен sorted(d.items(), key=...).

Сортируют список со смешанными типами, например числа вперемешку с None. В Python 3 это TypeError: сравнивать несравнимое язык больше не пытается. Выход в ключе, который явно задаёт место для None, например key=lambda x: (x is None, x).