sorted() function in Python - Time & Space Complexity

Time Complexity: sorted() function

O(n log n)

Understanding Time Complexity

When we use the sorted() function in Python, it rearranges items into order. Knowing how long this takes helps us understand how it behaves with bigger lists.

We want to find out how the time to sort grows as the list gets larger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

numbers = [5, 3, 8, 6, 2]
sorted_numbers = sorted(numbers)
print(sorted_numbers)

This code takes a list of numbers and creates a new list with the numbers sorted from smallest to largest.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Comparing and rearranging elements to sort the list.
• How many times: The sorting process compares elements many times, depending on the list size.

How Execution Grows With Input

As the list gets bigger, the number of comparisons and moves grows faster than the list size itself.

Input Size (n)	Approx. Operations
10	About 35 comparisons
100	About 700 comparisons
1000	About 10,000 comparisons

Pattern observation: When the list size grows 10 times, the work grows roughly 10 times, showing a growth faster than just the list size but consistent with O(n log n).

Final Time Complexity

Time Complexity: O(n log n)

This means the time to sort grows a bit faster than the list size but much slower than if it grew by the square of the list size.

Common Mistake

[X] Wrong: "Sorting always takes the same time no matter how big the list is."

[OK] Correct: Sorting takes more time as the list grows because it needs to compare and arrange more items, so bigger lists take longer.

Interview Connect

Understanding how sorting time grows helps you explain your code choices clearly and shows you know how your program behaves with bigger data.

Self-Check

"What if we used a list that was already sorted? How would the time complexity change when using sorted()?"