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()?"

Practice

1. What does the sorted() function do in Python?

easy

A. Returns a new list with items arranged in order

B. Changes the original list to be sorted

C. Deletes all items from the list

D. Returns the largest item in the list

Solution

1. Step 1: Understand the purpose of sorted()

   The sorted() function creates a new list with the elements arranged in ascending order by default.

2. Step 2: Compare with other options

   It does not change the original list, nor does it delete items or return just the largest item.

3. Final Answer:

   Returns a new list with items arranged in order -> Option A

4. Quick Check:

   sorted() returns new sorted list [OK]

Hint: Remember: sorted() returns a new list, original stays same [OK]

Common Mistakes:

• Thinking sorted() changes the original list
• Confusing sorted() with max() or min()
• Assuming sorted() deletes items

2. Which of the following is the correct syntax to sort a list nums in reverse order using sorted()?

easy

A. sorted(nums, reverse=False)

B. sorted(nums, reverse=0)

C. sorted(nums, reverse=false)

D. sorted(nums, reverse=True)

Solution

1. Step 1: Check the correct parameter for reverse sorting

   The sorted() function uses the keyword argument reverse=True to sort in descending order.

2. Step 2: Validate the parameter type

   The value must be the boolean True, not False, numbers like 0, or undefined names.

3. Final Answer:

   sorted(nums, reverse=True) -> Option D

4. Quick Check:

   Use reverse=True (boolean) for descending sort [OK]

Hint: Use reverse=True (boolean), not False/0/undefined [OK]

Common Mistakes:

• Using reverse=False (sorts ascending)
• Passing falsy numbers like 0
• Using undefined lowercase 'false'

3. What is the output of the following code?

words = ['pear', 'apple', 'orange']
sorted_words = sorted(words, key=len)
print(sorted_words)

medium

A. ['pear', 'apple', 'orange']

B. ['pear', 'apple', 'orange'] sorted by length

C. ['apple', 'orange', 'pear']

D. ['pear', 'apple', 'orange'] sorted by length ascending

Solution

1. Step 1: Understand the key parameter

   The key=len tells sorted() to sort the list by the length of each word.

2. Step 2: Sort words by length

   Lengths: 'pear' (4), 'apple' (5), 'orange' (6). Sorted ascending by length: ['pear', 'apple', 'orange'].

3. Final Answer:

   ['pear', 'apple', 'orange'] -> Option A

4. Quick Check:

   sorted(words, key=len) sorts by length ascending [OK]

Hint: key=len sorts items by their length ascending [OK]

Common Mistakes:

• Confusing sorting by value vs length
• Assuming sorted() changes original list
• Misreading the order of output

4. Find the error in this code snippet:

numbers = [3, 1, 4, 1, 5]
sorted_numbers = sorted(numbers, key='abs')
print(sorted_numbers)

medium

A. sorted() cannot sort numbers

B. Missing parentheses after sorted

C. key argument should be a function, not a string

D. reverse argument is required

Solution

1. Step 1: Check the key argument type

   The key parameter must be a function, like abs, not a string.

2. Step 2: Identify the error

   Here, key='abs' is a string, which causes a TypeError.

3. Final Answer:

   key argument should be a function, not a string -> Option C

4. Quick Check:

   key needs a function, not string [OK]

Hint: Pass function to key, not string name [OK]

Common Mistakes:

• Passing string instead of function to key
• Thinking sorted() can't sort numbers
• Forgetting parentheses in function calls

5. You have a list of tuples representing people and their ages:

people = [('Alice', 30), ('Bob', 25), ('Charlie', 35), ('David', 25)]

How do you use sorted() to sort this list by age ascending, and if ages are equal, by name alphabetically?

hard

A. sorted(people, key=lambda x: (x[0], x[1]))

B. sorted(people, key=lambda x: (x[1], x[0]))

C. sorted(people, key=lambda x: x[1])

D. sorted(people, key=lambda x: x[0])

Solution

1. Step 1: Understand sorting by multiple criteria

   To sort by age first, then by name if ages tie, use a tuple key with age first, then name.

2. Step 2: Write the key function

   The lambda lambda x: (x[1], x[0]) returns a tuple (age, name) for sorting.

3. Step 3: Check other options

   The option sorting by name then age is incorrect. Options sorting by only one field are wrong.

4. Final Answer:

   sorted(people, key=lambda x: (x[1], x[0])) -> Option B

5. Quick Check:

   Use tuple key (age, name) for multi-level sort [OK]

Hint: Use tuple in key: (age, name) for multi-level sorting [OK]

Common Mistakes:

• Sorting by name before age
• Using single key instead of tuple
• Confusing tuple order in key function