Python internal sort method [duplicate]

问题:

This question already has an answer here:

• About Python's built in sort() method 4 answers

Does anyone know what type of sort Python uses internally for list.sort()? Or that it at least guarantees O(n*log(n))? The docs don't say much. I was wondering after reading this question

回答1:

Python uses TimSort, a new algorithm developed by Tim Peters.

It is a O(NlogN) sorting algorithm, yes, both for the worst and average cases. In ideal situations it improves to O(N). See the Python Wiki Time Complexity page and the Wikipedia article I linked you to.

Note that the algorithm has proven quite popular and it has been added to Java SE 7, Android, and GNU Octave as well.