What is the complexity of the sorted() function?

Question

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?

Solution 1

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.

Solution 2

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.

Comments

[Steve Jessop]

And if you know the complexity of itemgetter(0) and it's not O(1) then you can still work out the overall complexity: sorted makes n calls to itemgetter(0) plus what you say.

[Nuclearman]

Doesn't Timsort have a best case of O(N).

[NPE]

@MC: It does. However, that's hardly relevant for practical use. Besides, any sorting algorithm can be made to have O(n) best case.

[Velda]

Relevant is also information, what is the best case. Here it is already sorted collection, which is good. So sorting already sorted array in Python should take O(n) time.