← Модуль collections · 🏠 Домой · Контекстные менеджеры →
Коротко. sorted() принимает любой iterable и возвращает новый список.
list.sort() сортирует список на месте и возвращает None.
lst = [3, 1, 2]
print(lst.sort(), lst)
# None [1, 2, 3]Возврат None — намеренное решение: так метод не спутать с функцией и не
написать lst = lst.sort(), потеряв данные. Это же правило действует
у reverse(), append(), extend().
Подвох. Классический вопрос «что вернёт lst.sort()» — именно про это.
И ещё: sorted() от словаря даст список ключей, а не пар — для пар
сортируют d.items().
Коротко. Через key — функцию одного аргумента, которая возвращает то,
по чему сравнивать. Для нескольких полей возвращают кортеж; направление
одного числового поля переворачивают минусом.
data = [("b", 2), ("a", 2), ("c", 1)]
sorted(data, key=lambda t: t[1]) # [('c', 1), ('b', 2), ('a', 2)]
sorted(data, key=lambda t: (-t[1], t[0])) # [('a', 2), ('b', 2), ('c', 1)]Вместо лямбд стандартная библиотека предлагает быстрые аналоги на C:
from operator import itemgetter, attrgetter
sorted(data, key=itemgetter(1)) # по элементу
sorted(users, key=attrgetter("last_name")) # по атрибуту
sorted(words, key=str.lower) # регистронезависимоПодвох. key вызывается ровно один раз на элемент (это decorate-sort-undecorate
внутри), поэтому дорогое вычисление в key дешевле, чем в компараторе. А вот
трюк «-t[1]» работает только для чисел: для строк направление разворачивают
только через reverse=True или через сортировку в два прохода.
Глубже. Компараторов в стиле cmp(a, b) в Python 3 нет — их убрали,
оставив functools.cmp_to_key() как мост для портирования старого кода:
sorted(xs, key=cmp_to_key(my_cmp)). Он оборачивает каждый элемент в объект
с переопределённым __lt__, поэтому заметно медленнее обычного key.
Коротко. Стабильность — элементы с равными ключами сохраняют исходный
взаимный порядок. Гарантируется и для sorted(), и для list.sort().
data = [("b", 2), ("a", 2), ("c", 1)]
sorted(data, key=lambda t: t[1])
# [('c', 1), ('b', 2), ('a', 2)] — 'b' осталось перед 'a'Практический смысл — многоуровневая сортировка последовательными проходами: сначала сортируют по второстепенному полю, затем по главному, и второстепенный порядок внутри групп сохраняется.
Подвох. reverse=True стабильность не ломает: это не разворот
результата, а сравнение в обратную сторону. Элементы с равными ключами
останутся в исходном порядке, а не перевернутся.
Коротко. Timsort — гибрид сортировки слиянием и вставками, придуманный
Тимом Питерсом для CPython. O(n log n) в худшем случае, O(n) на уже
отсортированных данных, память O(n), стабилен.
Идея: массив разбивается на «прогоны» (run) — уже упорядоченные участки. Короткие прогоны достраиваются вставками до минимальной длины, затем прогоны сливаются попарно по правилам, поддерживающим баланс стека. На почти отсортированных данных прогонов мало — и сортировка вырождается в линейный проход. Отсюда его популярность: Timsort перекочевал в Java (для объектов), Android, V8, Rust и Swift.
Подвох. Сравниваются именно ключи, и они должны быть сравнимы между собой. Разнотипный список падает:
sorted([1, "a"])
# TypeError: '<' not supported between instances of 'str' and 'int'Глубже. С Python 3.11 в CPython добавлена специализация: если все элементы
одного типа (int, float, str или кортежи из них), сортировка использует
предварительно выбранную быструю функцию сравнения вместо общего
PyObject_RichCompare — типовые случаи ускорились примерно в полтора-два раза
без изменения самого алгоритма.