What is the Python sort time 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))
I was wondering what is the runtime complexity of this Python function?
What is the Python sort time 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))
I was wondering what is the runtime complexity of this Python function?
I’ve been working with Python for years, and the time complexity of the sorted()
function is something I rely on a lot. In general, it’s O(n log n), where n
is the number of elements in the list.
This efficiency is thanks to Python’s use of Timsort—a hybrid algorithm derived from merge sort and insertion sort. Timsort is designed to handle real-world data efficiently, making sorted()
a solid choice for most scenarios.
Charity’s explanation is spot on, and I’d like to add how the key
parameter affects things. The complexity of sorted()
remains O(n log n) even when you use the key
parameter for custom sorting logic.
However, there’s a small overhead: the key function is applied to each element, which takes O(n). This evaluation happens before the sorting begins.
For instance:
from operator import itemgetter
data = [(3, 'a'), (1, 'b'), (2, 'c')]
sorted_data = sorted(data, key=itemgetter(0)) # Sort by the first element
print(sorted_data)
Here, the itemgetter(0)
is evaluated for every element before sorting. So while the overall complexity stays O(n log n), there’s a slight O(n) cost added for the key evaluation.