How does the built-in function "sorted" work in Python?

Question

x = [1, 4, 7, 65, 23, 57, 12]
>>> sorted(x)
[1, 4, 7, 12, 23, 57, 65]

Just out of curiosity, how does this function work? What is the algorithm that Python uses to sort iterables?

score 9 · Accepted Answer · edited May 23 '17 at 10:30

9

Python used to use Quicksort.

Then, the mighty Tim Peters came along, with a level 20 keyboard and coding chops that were over 9000; and in a magnificent symphony of elegance and brilliance, built Timsort and gifted it to us mere mortals, for our lives would be incomplete without it.

edited May 23 '17 at 10:30

Community

1
1

answered Dec 18 '13 at 07:47

inspectorG4dget

110,290
27
149
241

6

Timsort *cough* :) – Jon Clements Dec 18 '13 at 07:47
Yes, it's Timsort: http://en.wikipedia.org/wiki/Timsort – justhalf Dec 18 '13 at 07:48
http://svn.python.org/projects/python/trunk/Objects/listsort.txt – Kracekumar Dec 18 '13 at 07:49
No, it's not just "... Tim Peters came along ... ". It should be "... the mighty Tim Peters came along ...". :-) – Matthias Dec 18 '13 at 07:52
FWIW, No python implementation uses QuickSort these days for the simple reason that python's sort is (now) guaranteed to be stable. I believe that I heard a while back that IronPython uses MergeSort, but I haven't verified that myself (and the information might be outdated). – mgilson Dec 18 '13 at 07:52
@Matthias: how's that? – inspectorG4dget Dec 18 '13 at 08:35
2

@inspectorG4dget: Yeah, that's a pythonic explanation. – Matthias Dec 18 '13 at 08:55
1

Just noting that [the current version](http://hg.python.org/cpython/file/default/Objects/listsort.txt) of `listsort.txt` adds some notes to address common confusions. – Tim Peters Dec 18 '13 at 10:02

How does the built-in function "sorted" work in Python?

1 Answers1