CODEWITHSUNDEEP
pythonalgorithmsortingpython-internals
user89862
user89862

Reputation:

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?

Upvotes: 141

Views: 87247

Answers (3)

SirGavith
SirGavith

Reputation: 21

Since python version 3.11, sort() now uses a version of powersort, a merge-sort algorithm that takes advantage of runs: sequences of already-sorted values in the data. When the length is less than 64, python switches to binary insertion sort.

python implementation details: https://github.com/python/cpython/blob/main/Objects/listsort.txt

Upvotes: 2

Silfverstrom
Silfverstrom

Reputation: 29322

In early versions of Python, the sort function implemented a modified version of quicksort. However, in 2.3 this was replaced with an adaptive mergesort algorithm, in order to provide a stable sort by default.

Upvotes: 12

Alex Martelli
Alex Martelli

Reputation: 881595

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;-).

Upvotes: 151

Related Questions