Menu
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?
412
Time ComplexityBest Case – O(N log N) Average Case- O(N log N) Worse Case- O(N log N)
sort uses two sorting algorithms. One is a modification of Quicksort named dual-pivot quicksort, the other an adaptation of MergeSort named Timsort. Both have a time complexity of O(n log n) , where n is the total number of items in the array.
Python sorted() Function The sorted() function returns a sorted list of the specified iterable object. You can specify ascending or descending order. Strings are sorted alphabetically, and numbers are sorted numerically.
Sort vs Sorted Performance Here, sort() method is executing faster than sorted() function. Here, sorted() function method is executing faster than sort() function. There is also a difference in execution time in both cases.
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.
98
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.
39
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
