python - What is the complexity of the sorted() function?

54
votes

I have a list of lists and I am sorting them using the following

data=sorted(data, key=itemgetter(0))

Was wondering what is the runtime complexity of this python function?

3
pythonalgorithmsorting
The same as of a simple sorted. - eumiro
O(n log n) like just about every other comparison sort used in a language library. - Yuushi
en.wikipedia.org/wiki/Timsort - root
Timsort is a kind of adaptive sorting algorithm based on merge sort and insertion sort, then I thought it belongs to the comparison sort and no comparison sort can guarantee a time complexity smaller than lg(N!) ~ N log N. - Lerner Zhang

3 Answers

60
votes

Provided itemgetter(0) is O(1) when used with data, the sort is O(n log n) both on average and in the worst case.

For more information on the sorting method used in Python, see Wikipedia.

2
votes

sorted is like sort except that the first builds a new sorted list from an iterable while sort do sort in place. The main difference will be space complexity.

0
votes

It is the Timsort, and Timsort is a kind of adaptive sorting algorithm based on merge sort and insertion sort, then I thought it belongs to the comparison sort, and it's said, no comparison sort can guarantee a time complexity smaller than lg(N!) ~ N log N.