Кратко о поведении
- Ключ сортировки — $(x\mathrm{mod}2,x)$. Это означает: сначала сравнивается остаток от деления на два (четность), затем само значение. В результате все чётные элементы идут перед нечётными, внутри каждой группы — возрастающая сортировка по значению.
Примеры
- Вход $[3,1,4,2,5]$ → выход $[2,4,1,3,5]$.
- Вход $[-3,-2,-1,0,1]$ → выход $[-2,0,-3,-1,1]$ (парность в Python: $-1\mathrm{mod}2=1$).
Сложность
- Время: сортировка в CPython использует Timsort, худший/средний случай $O(n\log n)$, лучший случай (много уже упорядоченных «run») — $O(n)$.
- Оценка вызова ключа: ключ вычисляется один раз для каждого элемента (DSU), поэтому дополнительный труд по ключам — $O(n)$.
- Память: требуется дополнительная память для нового списка и для хранимых ключей — $O(n)$.
- Стабильность: сортировка стабильна (относительный порядок элементов с равными ключами сохраняется).
Практические применения
- Быстрая группировка по чётности с сортировкой внутри групп (например, вывод всех чётных сначала, затем нечётных).
- Пример общего приёма: сортировка по нескольким критериям (сначала приоритетная категория, затем вторичный ключ).
- Удобно в коде для кратких однострочных преобразований списков.
Ограничения и подводные камни
- Типы данных: сравнение по второму компоненту ключа требует, чтобы значения были сопоставимы между собой (смесь несовместимых типов может вызвать TypeError).
- Числа с плавающей точкой: $x\mathrm{mod}2$ для float даёт дробный остаток (не обязательно $0$ или $1$), поэтому поведение для float-значений отличается от целочисленного деления.
- Для комплексных чисел сравнение по $x$ невозможно — приведёт к ошибке.
- Память: если нужно только разделить на чётные/нечётные без полной сортировки, более эффективен одноразовый проход за $O(n)$ с $O(1)$ дополнительной памятью или с двумя отдельными сортировками меньших подмножеств.
- Если нужен порядок «нечётные сначала», достаточно изменить ключ, напр.: $(1-(x\mathrm{mod}2),x)$ или $(x\mathrm{mod}2==0,x)$.
Вывод
- Функция делает простую и понятную двухкритериальную сортировку: чётность затем значение; асимптотика типична для сортировок на основе Timsort: $O(n\log n)$ (в среднем), память $O(n)$. Подходит для случая, когда нужно именно «evens then odds» и упорядоченность внутри групп; не годится для несравнимых типов, для float-остатков или когда важна экономия памяти/времени (тогда лучше разделить и сортировать группы отдельно или выполнить однопроходную партицию).