Sorting Stability and When to Use Which Sort in DSA Python - Execution Trace

Concept Flow - Sorting Stability and When to Use Which Sort

Start with unsorted array

↓

Choose sorting algorithm

↓

Check if stability needed?

Yes→Use stable sort

↓

Use unstable sort

↓

Sort array

↓

Sorted array with/without stability

↓

Done

Start with an unsorted list, decide if you need to keep equal items' order (stability), then pick a stable or unstable sort accordingly, and finally get the sorted list.

Execution Sample

DSA Python

arr = [(4, 'a'), (3, 'b'), (4, 'c'), (2, 'd')]
# Sort by first element, stable sort keeps 'a' before 'c'
sorted_arr = sorted(arr, key=lambda x: x[0])
print(sorted_arr)

Sort a list of pairs by the first number using a stable sort to keep original order of equal elements.

Execution Table

Step	Operation	Array State	Stability Effect	Visual State
0	Initial array	[(4, 'a'), (3, 'b'), (4, 'c'), (2, 'd')]	N/A	[4a, 3b, 4c, 2d]
1	Compare (4a) and (3b)	[(4, 'a'), (3, 'b'), (4, 'c'), (2, 'd')]	Swap to move smaller element forward	[3b, 4a, 4c, 2d]
2	Compare (4a) and (4c)	[(3, 'b'), (4, 'a'), (4, 'c'), (2, 'd')]	No swap, order unchanged	[3b, 4a, 4c, 2d]
3	Compare (4c) and (2d)	[(3, 'b'), (4, 'a'), (4, 'c'), (2, 'd')]	Swap to move smaller element forward	[3b, 4a, 2d, 4c]
4	After first pass	[(3, 'b'), (2, 'd'), (4, 'a'), (4, 'c')]	Stable sort keeps (4a) before (4c)	[3b, 2d, 4a, 4c]
5	Final sorted array	[(2, 'd'), (3, 'b'), (4, 'a'), (4, 'c')]	Stable: equal keys keep original order	[2d, 3b, 4a, 4c]

💡 Sorting complete with stability preserving order of equal elements

Variable Tracker

Variable	Start	After Step 3	After Step 5 (Final)
arr	[(4, 'a'), (3, 'b'), (4, 'c'), (2, 'd')]	[(3, 'b'), (4, 'a'), (2, 'd'), (4, 'c')]	[(2, 'd'), (3, 'b'), (4, 'a'), (4, 'c')]
sorted_arr	N/A	N/A	[(2, 'd'), (3, 'b'), (4, 'a'), (4, 'c')]

Key Moments - 3 Insights

Why does the stable sort keep (4, 'a') before (4, 'c') even though they have the same key?

Because stable sorts do not change the relative order of equal elements, as shown in execution_table rows 4 and 5 where (4, 'a') stays before (4, 'c').

What happens if we use an unstable sort on the same array?

The order of equal keys like (4, 'a') and (4, 'c') might change, losing the original sequence, unlike the stable sort shown in the execution_table.

When should we choose a stable sort over an unstable sort?

Choose stable sort when the order of equal elements matters, for example when sorting by multiple criteria step-by-step, as stability preserves previous order.

Visual Quiz - 3 Questions

Look at the execution_table at Step 5, what is the order of elements with key 4?

A [(4, 'c'), (4, 'a')]

B [(4, 'a'), (3, 'b')]

C [(4, 'a'), (4, 'c')]

D [(3, 'b'), (4, 'c')]

💡 Hint

Check the Visual State column at Step 5 in execution_table

At which step does the first swap happen in the sorting process?

A Step 4

B Step 1

C Step 3

D Step 5

💡 Hint

Look for 'Swap' in the Stability Effect column in execution_table

If stability was not required, which sorting algorithm could be faster but unstable?

A Quick Sort

B Bubble Sort

C Merge Sort

D Insertion Sort

💡 Hint

Quick Sort is known for speed but is generally unstable

Concept Snapshot

Sorting Stability:
- Stable sort keeps equal elements in original order.
- Unstable sort may reorder equal elements.
When to use:
- Use stable sort if order matters (e.g., multi-level sorting).
- Use unstable sort for speed if order doesn't matter.
Examples: Merge Sort (stable), Quick Sort (unstable).

Full Transcript

Sorting stability means that when sorting items with equal keys, a stable sort keeps their original order, while an unstable sort may change it. This matters when sorting by multiple criteria or when the order of equal items carries meaning. For example, sorting pairs by the first number with a stable sort keeps pairs with the same number in the order they appeared. When choosing a sorting algorithm, use stable sorts like Merge Sort if order preservation is important. Use faster but unstable sorts like Quick Sort if order does not matter. The execution trace shows how a stable sort preserves order of equal elements step-by-step.

Practice

1. What does it mean when a sorting algorithm is called stable?

easy

A. It keeps the original order of equal elements unchanged.

B. It sorts the elements in ascending order only.

C. It uses less memory than unstable sorts.

D. It always sorts in place without extra space.

Solution

1. Step 1: Understand stability in sorting

   A stable sort keeps elements with the same value in the same order as they appeared originally.

2. Step 2: Compare options with definition

   Only It keeps the original order of equal elements unchanged. describes this property correctly. Other options describe different concepts.

3. Final Answer:

   It keeps the original order of equal elements unchanged. -> Option A

4. Quick Check:

   Stable sort = keeps order of equal elements [OK]

Hint: Stable means equal items keep their original order [OK]

Common Mistakes:

• Confusing stability with sorting order
• Thinking stability means less memory use
• Assuming all sorts are stable

2. Which of the following Python sorting methods is stable by default?

easy

A. sorted() function

B. list.sort() method

C. Neither sorted() nor list.sort()

D. Both sorted() and list.sort()

Solution

1. Step 1: Recall Python sorting stability

   Both sorted() and list.sort() use Timsort, which is stable.

2. Step 2: Check options

   Options A and B are each correct alone, but Both sorted() and list.sort() correctly states both are stable.

3. Final Answer:

   Both sorted() and list.sort() -> Option D

4. Quick Check:

   Python sorts are stable by default [OK]

Hint: Python's built-in sorts are stable by default [OK]

Common Mistakes:

• Thinking only one method is stable
• Confusing stability with sorting order
• Assuming custom sorts are stable by default

3. Consider this list of tuples representing (name, score):

data = [("Alice", 90), ("Bob", 90), ("Charlie", 85)]

What will be the output after sorting by score using sorted(data, key=lambda x: x[1])?

medium

A. [('Charlie', 85), ('Bob', 90), ('Alice', 90)]

B. [('Alice', 90), ('Bob', 90), ('Charlie', 85)]

C. [('Charlie', 85), ('Alice', 90), ('Bob', 90)]

D. [('Bob', 90), ('Alice', 90), ('Charlie', 85)]

Solution

1. Step 1: Understand sorting by score

   The sort uses the second item (score) as key, sorting ascending: 85, 90, 90.

2. Step 2: Check stability for equal scores

   Since Python's sort is stable, 'Alice' and 'Bob' keep their original order for score 90.

3. Final Answer:

   [('Charlie', 85), ('Alice', 90), ('Bob', 90)] -> Option C

4. Quick Check:

   Stable sort keeps 'Alice' before 'Bob' [OK]

Hint: Stable sort keeps original order for equal keys [OK]

Common Mistakes:

• Swapping order of equal elements
• Sorting descending by mistake
• Ignoring stability property

4. You wrote this code to sort a list of dictionaries by 'age':

people = [{'name': 'Ann', 'age': 25}, {'name': 'Ben', 'age': 20}, {'name': 'Cara', 'age': 25}]
people.sort(key=lambda x: x['age'])
print(people)

But the output does not keep the original order of people with the same age. What is the likely cause?

medium

A. The key function is incorrect.

B. The dictionaries are unordered, causing instability.

C. The list.sort() method is stable, so no cause.

D. The sort method used is unstable.

Solution

1. Step 1: Recall Python sort stability

   Python's list.sort() is stable, so it keeps order of equal keys.

2. Step 2: Understand dictionary order

   Before Python 3.7, dictionaries did not preserve insertion order, so printing may show different order.

3. Step 3: Identify cause

   If using older Python or unordered dicts, the printed order may seem unstable even if sort is stable.

4. Final Answer:

   The dictionaries are unordered, causing instability. -> Option B

5. Quick Check:

   Unordered dicts can hide stable sort [OK]

Hint: Unordered dicts can hide stable sort effects [OK]

Common Mistakes:

• Blaming sort method instead of dict order
• Changing key function unnecessarily
• Ignoring Python version differences

5. You have a list of student records with (name, grade, age). You want to sort by grade ascending, then by age descending, but keep the original order for students with same grade and age. Which sorting approach is best?

hard

A. Use a stable sort twice: first by age descending, then by grade ascending.

B. Use an unstable sort once with a combined key (grade, -age).

C. Use a stable sort once with key (grade, age).

D. Sort by age ascending, then by grade descending using stable sorts.

Solution

1. Step 1: Understand multi-level sorting with stability

   To sort by multiple keys and keep original order for ties, use stable sorts starting from the last key.

2. Step 2: Apply sorting order

   First sort by age descending (second key), then by grade ascending (first key), both stable.

3. Step 3: Check options

   Use a stable sort twice: first by age descending, then by grade ascending. matches this approach. Others either use unstable sort or wrong key order.

4. Final Answer:

   Use a stable sort twice: first by age descending, then by grade ascending. -> Option A

5. Quick Check:

   Stable sorts chained preserve multi-key order [OK]

Hint: Sort by last key first with stable sort, then first key [OK]

Common Mistakes:

• Sorting keys in wrong order
• Using unstable sort for multi-key sorting
• Ignoring descending order for age