О встроенном в Python методе sort ()

Question

Какой алгоритм использует встроенный метод sort() в Python? Можно ли взглянуть на код этого метода?

Answer 1

Конечно! Код здесь , начиная с функции islt и продолжая некоторое время ;-). Как говорит комментарий Криса, это C-код. Вам также нужно прочитать этот текстовый файл для текстового объяснения, результатов и т. Д. И т. Д.

Если вы предпочитаете читать код Java, а не код C, вы можете взглянуть на реализацию TimSort Джошуа Блоха в Java и для нее (Джошуа также разработал в 1997 году модифицированную сортировку слиянием, которая все еще используется в Java, и можно надеяться, что что Java в конечном итоге переключится на его недавний порт timsort).

Некоторое объяснение Java-порта timsort: здесь , разность здесь (с указателями на все необходимые файлы), файл ключа здесь - FWIW, хотя я лучше программист на C, чем программист на Java, в этом случае я нахожу Java-код Джошуа более читабельным, чем код C Тима; -).

Answer 2

Я просто хотел предоставить очень полезную ссылку, которую я упустил в исчерпывающем ответе Алекса: Высокоуровневое объяснение тимсорта Python (с визуализацией графов!).

(Да, алгоритм в основном известен как Timsort сейчас)

Answer 3

В ранних версиях Python функция sort реализовала модифицированную версию быстрой сортировки. Однако он считался нестабильным, и с версии 2.3 они перешли на использование адаптивного алгоритма слияния.

Answer 4

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