3

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

Community
  • 1
  • 1
Hari Ganesan
  • 532
  • 4
  • 18

1 Answers1

8

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.

Martijn Pieters
  • 1,048,767
  • 296
  • 4,058
  • 3,343