128

What algorithm is the built in sort() method in Python using? Is it possible to have a look at the code for that method?

Martijn Pieters
  • 963,270
  • 265
  • 3,804
  • 3,187
Johannes
  • 11,096
  • 20
  • 68
  • 85
  • 12
    Of course it's possible to look at the code for the method - Python is an open-source project. The method is probably implemented in C, however, so you'll have to know a bit about C to make any sense of it. – Chris Lutz Oct 04 '09 at 20:50
  • Does the version matter? – meder omuraliev Oct 04 '09 at 20:50
  • @melder: No =) I just want to have a look at a pro algorithm :P @chris: how? – Johannes Oct 04 '09 at 20:51
  • 3
    Download the source code to the Python interpreter. I don't know where they implement the `sort()` method, or what the formatting to the interpreter is, but it's got to be in there somewhere, and I bet it's implemented in C for speed concerns. – Chris Lutz Oct 04 '09 at 20:54
  • [Here](http://stackoverflow.com/questions/36139/how-do-i-sort-a-list-of-strings-in-python) is an example of it being used – Hari Ganesan Feb 04 '14 at 17:21

3 Answers3

141

Sure! The code's here, starting with function islt and proceeding for QUITE a while;-). As Chris's comment suggests, it's C code. You'll also want to read this text file for a textual explanation, results, etc etc.

If you prefer reading Java code than C code, you could look at Joshua Bloch's implementation of timsort in and for Java (Joshua's also the guy who implemented, in 1997, the modified mergesort that's still used in Java, and one can hope that Java will eventually switch to his recent port of timsort).

Some explanation of the Java port of timsort is here, the diff is here (with pointers to all needed files), the key file is here -- FWIW, while I'm a better C programmer than Java programmer, in this case I find Joshua's Java code more readable overall than Tim's C code;-).

Stephen Fuhry
  • 11,930
  • 6
  • 52
  • 55
Alex Martelli
  • 811,175
  • 162
  • 1,198
  • 1,373
  • 4
    @Chris, "Browse Python sources" is a shortcut in all of my browsers' bookmark bars -- it points to http://svn.python.org/view/python/trunk/ ;-). – Alex Martelli Oct 04 '09 at 21:05
  • I want to know what the function `list_ass_item()` does. :) – Chris Lutz Oct 04 '09 at 21:10
  • 2
    Performs assignment to an item of the list (just like list_ass_slice performs assignment to a slice of the list), nothing to do with sorting. I guess the abbreviation of "assignment" makes the name funny... – Alex Martelli Oct 04 '09 at 23:22
  • 3
    [The current version](http://hg.python.org/cpython/file/default/Objects/listsort.txt) of `listsort.txt` adds some notes that address common confusions. – Tim Peters Dec 18 '13 at 10:03
40

I just wanted to supply a very helpful link that I missed in Alex's otherwise comprehensive answer: A high-level explanation of Python's timsort (with graph visualizations!).

(Yes, the algorithm is basically known as Timsort now)

twasbrillig
  • 14,704
  • 9
  • 39
  • 61
u0b34a0f6ae
  • 45,417
  • 14
  • 88
  • 100
10

In early python-versions, the sort function implemented a modified version of quicksort. However, it was deemed unstable and as of 2.3 they switched to using an adaptive mergesort algorithm.

Silfverstrom
  • 26,646
  • 6
  • 44
  • 56
  • 1
    quicksort isn't 'deemed unstable' - by the commonly used definitions, quicksort is unstable - that is the original ordering of two objects is not preserved, if they are equal during this sort. Having an unstable sort algorithm means that you have to come up with all sorts of 'magic' to sensibly sort data with multiple criteria, rather than then simply being able to chain sort calls - in timsort if you want to sort by D.O.B and then name, you simply sort by name first, and then D.O.B. You can't do that with quicksort – Tony Suffolk 66 Jul 30 '20 at 06:19