Does anyone know what type of type 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
Python uses TimSort , a new algorithm developed by Tim Peters.
This is an O (NlogN) sorting algorithm, yes, for both worst and average cases. In ideal situations, it improves to O (N). See Page