Sorting and reversing lists in Python - Time & Space Complexity

Time Complexity: Sorting and reversing lists

O(n log n)

Understanding Time Complexity

When we sort or reverse lists, we want to know how the time needed grows as the list gets bigger.

We ask: How much longer does it take if the list doubles or triples in size?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

my_list = [5, 3, 8, 1, 2]
my_list.sort()
my_list.reverse()

This code sorts a list in ascending order, then reverses it to get descending order.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Sorting the list, which compares and moves elements multiple times.
• How many times: The sorting process repeats comparisons roughly proportional to n log n of the list size.
• Reversing: Goes through the list once to swap elements from ends to middle.

How Execution Grows With Input

Sorting takes more time as the list grows, but reversing grows more slowly.

Input Size (n)	Approx. Operations
10	About 30 to 50 for sorting, 10 for reversing
100	About 600 to 700 for sorting, 100 for reversing
1000	About 10,000 to 14,000 for sorting, 1,000 for reversing

Pattern observation: Sorting grows much faster than reversing as list size increases.

Final Time Complexity

Time Complexity: O(n log n)

This means sorting takes longer as the list grows, but not as fast as checking every pair; reversing just goes through the list once.

Common Mistake

[X] Wrong: "Reversing a list takes as long as sorting it."

[OK] Correct: Reversing only swaps elements once each, so it takes much less time than sorting, which compares many pairs.

Interview Connect

Understanding how sorting and reversing scale helps you explain your choices clearly and shows you know what happens behind the scenes.

Self-Check

"What if we used a different sorting method like bubble sort instead of the built-in sort? How would the time complexity change?"

Practice

1. What does the list.sort() method do to a list in Python?

easy

A. It arranges the list items in ascending order.

B. It reverses the order of the list items.

C. It removes duplicate items from the list.

D. It creates a new sorted list without changing the original.

Solution

1. Step 1: Understand the purpose of list.sort()

   The list.sort() method changes the original list to arrange its items in ascending order.

2. Step 2: Differentiate from other list methods

   Unlike list.reverse(), which flips the list order, list.sort() orders items from smallest to largest.

3. Final Answer:

   It arranges the list items in ascending order. -> Option A

4. Quick Check:

   list.sort() = ascending order [OK]

Hint: Remember: sort() orders ascending by default [OK]

Common Mistakes:

• Confusing sort() with reverse()
• Thinking sort() returns a new list
• Assuming sort() removes duplicates

2. Which of the following is the correct syntax to sort a list named numbers in descending order?

easy

A. numbers.sort(reverse=True)

B. numbers.sort(reverse=1)

C. numbers.sort(descending=True)

D. numbers.reverse(sort=True)

Solution

1. Step 1: Identify correct parameter for descending sort

   The sort() method accepts reverse=True to sort in descending order.

2. Step 2: Check syntax correctness

   numbers.sort(reverse=True) uses the correct syntax: numbers.sort(reverse=True). Other options use invalid parameters or method calls.

3. Final Answer:

   numbers.sort(reverse=True) -> Option A

4. Quick Check:

   sort(reverse=True) = descending order [OK]

Hint: Use reverse=True inside sort() for descending order [OK]

Common Mistakes:

• Using reverse=1 instead of reverse=True
• Using non-existent parameters like descending=True
• Calling reverse() with parameters

3. What is the output of the following code?

items = [3, 1, 4, 2]
items.sort()
items.reverse()
print(items)

medium

A. [1, 2, 3, 4]

B. [3, 1, 4, 2]

C. [4, 3, 2, 1]

D. [2, 3, 1, 4]

Solution

1. Step 1: Apply items.sort()

   This sorts the list in ascending order: [1, 2, 3, 4].

2. Step 2: Apply items.reverse()

   This reverses the sorted list, resulting in [4, 3, 2, 1].

3. Final Answer:

   [4, 3, 2, 1] -> Option C

4. Quick Check:

   sort() then reverse() = descending list [OK]

Hint: sort() then reverse() = descending order [OK]

Common Mistakes:

• Thinking reverse() sorts the list
• Assuming print shows original list
• Confusing order of method calls

4. The following code is intended to sort the list data in descending order. What is wrong?

data = [5, 2, 9, 1]
data.reverse()
data.sort()
print(data)

medium

A. The code will cause a syntax error.

B. The reverse() call should come after sort().

C. The sort() method does not exist for lists.

D. The list is already sorted, so no change happens.

Solution

1. Step 1: Analyze method order

   The code reverses the list first, then sorts it ascending, which cancels the reverse effect.

2. Step 2: Correct method order for descending sort

   To get descending order, first sort ascending, then reverse the list.

3. Final Answer:

   The reverse() call should come after sort(). -> Option B

4. Quick Check:

   sort() then reverse() = descending order [OK]

Hint: Sort first, then reverse for descending order [OK]

Common Mistakes:

• Reversing before sorting cancels sorting effect
• Thinking reverse() sorts the list
• Assuming method order does not matter

5. You have a list of words: words = ['apple', 'banana', 'cherry', 'date']. You want to sort them in reverse alphabetical order without changing the original list. Which code snippet achieves this?

hard

A. sorted_words = words.sort(reverse=True)

B. words.sort(reverse=True)

C. words.reverse(); words.sort()

D. sorted_words = sorted(words, reverse=True)

Solution

1. Step 1: Understand difference between sort() and sorted()

   sort() changes the original list; sorted() returns a new sorted list.

2. Step 2: Choose method that sorts in reverse without changing original

   Using sorted(words, reverse=True) returns a new list sorted in reverse alphabetical order, leaving words unchanged.

3. Final Answer:

   sorted_words = sorted(words, reverse=True) -> Option D

4. Quick Check:

   sorted() returns new sorted list [OK]

Hint: Use sorted() to keep original list unchanged [OK]

Common Mistakes:

• Using sort() which changes original list
• Chaining reverse() before sort() incorrectly
• Assigning sort() result which is None