What is the complexity of this python sort method?


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 method?

1/21/2013 7:59:30 AM

Accepted Answer

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.

1/21/2013 9:08:42 AM

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.

Licensed under: CC-BY-SA with attribution
Not affiliated with: Stack Overflow