Какой алгоритм использует Python sorted ()? [Дубликат]

Possible Duplicate:
About python's built in sort() method

Имя говорит само за себя.

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

Если это имеет значение, мы говорим на Python 2.7.

 Hartley Brody08 июн. 2012 г., 15:54
Для тех, кому интересно, эта статья отлично подходит:corte.si//posts/code/timsort/index.html
 Aharpe08 июн. 2012 г., 14:36
stackoverflow.com/questions/1517347/… Вопрос был дан ответ здесь. Это использует Timsort

Ответы на вопрос(3)

Решение Вопроса

Python использует алгоритм под названиемTimsort:

Timsort is a hybrid sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data. It was invented by Tim Peters in 2002 for use in the Python programming language. The algorithm finds subsets of the data that are already ordered, and uses the subsets to sort the data more efficiently. This is done by merging an identified subset, called a run, with existing runs until certain criteria are fulfilled. Timsort has been Python's standard sorting algorithm since version 2.3. It is now also used to sort arrays in Java SE 7, and on the Android platform.

 25 февр. 2015 г., 15:18
В интересной статье говорится, что она обнаружила ошибку в TimSort (и исправляет ее):envisage-project.eu/…
 08 июн. 2012 г., 14:37
Это очень впечатляющий алгоритм: другу ОП было бы очень трудно разработать что-то лучшее самостоятельно.
 08 июн. 2012 г., 14:40
Он не только использует чрезвычайно умный алгоритм, но и реализует его на оптимизированном вручную языке C. Даже если бы вы реализовали его самостоятельно, переведя псевдокод на Python, он был бы на порядок медленнее и требовал больше памяти.
 25 нояб. 2017 г., 14:14
@bgporter Если быть точным, ошибка была не в Timsort, а в его эталонной реализации. СогласноWikipedia article, это уже исправлено.

Алгоритм сортировки называется Timsort. Увидетьtimsort

Начиная с 2.3 Python использует timsort.

Больше информации:http://bugs.python.org/file4451/timsort.txt

Ваш ответ на вопрос