Гарантируется ли стабильность функции sorted () Python?

Документация не гарантирует , что. Есть ли другое место, где это задокументировано?

Я предполагаю, что он может быть стабильным, так как метод sort в списках гарантированно стабилен (примечания 9 пункт: «Начиная с Python 2.3, метод sort () гарантированно стабилен»), а sorted функционально аналогичен. Однако я не могу найти какой-либо исчерпывающий источник, в котором говорится об этом.

Цель: мне нужно выполнить сортировку на основе первичного ключа, а также вторичного ключа в тех случаях, когда первичный ключ одинаков в обеих записях. Если sorted () гарантированно будет стабильным, я могу отсортировать по вторичному ключу, затем отсортировать по первичному ключу и получить нужный мне результат.

PS: Чтобы избежать путаницы, я использую стабильный в смысле «сортировка стабильна, если она гарантирует, что не изменит относительный порядок элементов, которые сравниваются равными».

Да, цель руководства действительно состоит в том, чтобы гарантировать sortedстабильность и использование того же алгоритма, что и sortметод. Я действительно понимаю, что документы не на 100% ясны об этой личности; doc патчи всегда с радостью принимаются!

Они стабильны .

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

Например, если вы хотите , чтобы отсортировать объекты на основе их last_name, first_nameатрибутов, вы можете сделать это за один проход:

sorted_list= sorted(
    your_sequence_of_items,
    key= lambda item: (item.last_name, item.first_name))

пользуясь преимуществом сравнения кортежей.

Этот ответ как есть охватывает исходный вопрос. Для дальнейших вопросов, связанных с сортировкой, есть руководство по сортировке Python .

Тем временем документация была изменена ( соответствующий коммит ), и текущая документация sortedявно гарантирует это:

sorted()Гарантированная стабильность встроенной функции. Сортировка является стабильной, если она гарантирует не изменить относительный порядок сравниваемых элементов - это полезно для сортировки за несколько проходов (например, сортировка по отделам, а затем по разряду зарплаты).

Эта часть документации была добавлена ​​в Python 2.7 и Python 3.4 (+), поэтому любая совместимая реализация этой языковой версии должна иметь стабильнуюsorted .

Обратите внимание, что для CPython list.sortон был стабильным с Python 2.3.

• Тим Петерс переписал свою list.sort()реализацию - это «стабильная сортировка» (одинаковые входные данные появляются в одном и том же порядке на выходе) и быстрее, чем раньше.

Я не уверен на 100% sorted, в настоящее время он прост в использовании list.sort, но я не проверял историю на предмет этого. Но вполне вероятно, что его «всегда» использовали list.sort.

Документы «Что нового» для Python 2.4 фактически указывают на то, что sorted () сначала создает список, а затем вызывает для него sort (), предоставляя вам необходимую гарантию, хотя и не в «официальных» документах. Вы также можете просто проверить источник, если вас действительно беспокоит.

В документе Python 3.6 о сортировке теперь говорится, что

Сорта гарантированно стабильны

Кроме того, в этом документе есть ссылка на стабильную версию Timsort , в которой говорится, что

Timsort - стандартный алгоритм сортировки Python с версии 2.3.