150

In Python 2.7, how does Python's built-in sorted function work - what algorithm does it use?

Karl Knechtel
  • 62,466
  • 11
  • 102
  • 153
Hartley Brody
  • 8,669
  • 14
  • 37
  • 48
  • 4
    http://stackoverflow.com/questions/1517347/about-pythons-built-in-sort-method Question has been answered here. It uses Timsort – Aharpe Jun 08 '12 at 12:36
  • For others who are curious, this article is great: http://corte.si//posts/code/timsort/index.html – Hartley Brody Jun 08 '12 at 13:54
  • @HartleyBrody, the link is broken. Are you referring to https://corte.si/posts/code/timsort/ or https://corte.si/posts/code/timsort-grayscale/ ? – heretoinfinity Dec 19 '22 at 14:47

3 Answers3

256

Python uses an algorithm called 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.

bgporter
  • 35,114
  • 8
  • 59
  • 65
  • 18
    It's a very impressive algorithm: the OP's friend would be very hard-pressed to develop something better on their own. – Daniel Roseman Jun 08 '12 at 12:37
  • 35
    Not only does it use an extremely clever algorithm, is also implements it in hand-optimized C. Even if you implemented it yourself by translating the pseudocode into Python, it would be an order of magnitude slower and more memory-hungry. –  Jun 08 '12 at 12:40
  • 4
    An interesting paper says that it's found a bug in TimSort (and provides a fix for it): http://envisage-project.eu/proving-android-java-and-python-sorting-algorithm-is-broken-and-how-to-fix-it/ – bgporter Feb 25 '15 at 14:18
  • 8
    @bgporter To be precise, the bug was not in Timsort, but in its reference implementation. According to the [Wikipedia article](https://en.wikipedia.org/wiki/Timsort#Formal_verification), it has been fixed already. – SergiyKolesnikov Nov 25 '17 at 13:14
15

The sort algorithm is called Timsort. See timsort

Pierce
  • 564
  • 2
  • 8
13

Since 2.3 Python has used timsort.

More info: http://bugs.python.org/file4451/timsort.txt

David Haynes
  • 933
  • 5
  • 14