'What is the complexity of the sorted() function?

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?

pythonalgorithmsorting


Solution 1:[1]

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.

Solution 2:[2]

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.

Solution 3:[3]

Just like in every other programming language, the sorted() has O(NlogN) Time Complexity.

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 blackmath
Solution 2 Lerner Zhang
Solution 3 Fahad Nadeem

Related Questions