pythonalgorithmsortingpython-internals

What algorithm does Python's built-in sort() method use?

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

Solution

  • Sure! The code's here: listobject.c, starting with function islt and proceeding for QUITE a while ;-). As the file extension suggests, it's C code. You'll also want to read this for a textual explanation, results, etc etc: listsort.txt

    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 in this request for enhancement1, the diff is here2 (with pointers to all needed files), the key file is here3 -- 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 ;-).

    Editor's notes

    1. Archive link: Bug ID: 6804124 - Replace "modified mergesort" in java.util.Arrays.sort with timsort
    2. Archive link: jdk7/tl/jdk: changeset 1423:bfd7abda8f79 (6804124)
    3. Dead link. This may be the modern equivalent but I don't know Java: TimSort.java at master - openjdk/jdk