Hi! What algorithm is the built in sort() method in python using? Is it possible to have a look at the code for that method?
Thanks =)
+2
A:
In early python-versions, the sort function implemented an modified version of quicksort. However, it was deemed unstable and as of 2.3 they switched to using an adaptive mergesort algorithm.
Silfverstrom
2009-10-04 20:52:09
+10
A:
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;-).
Alex Martelli
2009-10-04 20:53:10
+1 for knowing where it was.
Chris Lutz
2009-10-04 20:55:48
@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
2009-10-04 21:05:14
I want to know what the function `list_ass_item()` does. :)
Chris Lutz
2009-10-04 21:10:54
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
2009-10-04 23:22:04
+1
A:
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)
kaizer.se
2009-10-04 23:03:41