Sorting Stability and When to Use Which Sort in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of stable sort on this list?

Consider the list of tuples representing (name, score):

[('Alice', 90), ('Bob', 85), ('Charlie', 90), ('David', 85)]

If we sort this list by score using a stable sorting algorithm, what will be the order of elements after sorting?

DSA Python

data = [('Alice', 90), ('Bob', 85), ('Charlie', 90), ('David', 85)]
sorted_data = sorted(data, key=lambda x: x[1])
print(sorted_data)

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

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

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

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

💡 Hint

Remember that stable sort keeps the original order of equal elements.

Stable sort keeps the relative order of elements with equal keys. Here, 'Bob' and 'David' both have score 85, and 'Bob' comes before 'David' originally, so 'Bob' stays before 'David' after sorting.

🧠 Conceptual

intermediate

Which sorting algorithm is stable by default?

Among the following sorting algorithms, which one is stable by default?

A Merge Sort

B Heap Sort

C Quick Sort

D Selection Sort

💡 Hint

Think about which algorithm merges sorted sublists without changing order of equal elements.

Merge Sort is stable because it merges sorted lists by comparing elements and preserving their order when equal.

❓ Predict Output

advanced

What error or output does this unstable sort produce?

Given the list of objects with duplicate keys, what is the output after sorting with an unstable algorithm?

data = [{'id': 1, 'value': 10}, {'id': 2, 'value': 5}, {'id': 3, 'value': 10}, {'id': 4, 'value': 5}]
# Sort by 'value' using an unstable sort

DSA Python

data = [{'id': 1, 'value': 10}, {'id': 2, 'value': 5}, {'id': 3, 'value': 10}, {'id': 4, 'value': 5}]
# Simulate unstable sort by sorting with a custom unstable method
# For demonstration, we use sorted but shuffle equal elements manually
sorted_data = sorted(data, key=lambda x: x['value'])
# Manually swap equal elements to simulate instability
sorted_data[0], sorted_data[1] = sorted_data[1], sorted_data[0]
print(sorted_data)

A [{'id': 2, 'value': 5}, {'id': 4, 'value': 5}, {'id': 1, 'value': 10}, {'id': 3, 'value': 10}]

B [{'id': 2, 'value': 5}, {'id': 4, 'value': 5}, {'id': 3, 'value': 10}, {'id': 1, 'value': 10}]

C [{'id': 4, 'value': 5}, {'id': 2, 'value': 5}, {'id': 3, 'value': 10}, {'id': 1, 'value': 10}]

D [{'id': 4, 'value': 5}, {'id': 2, 'value': 5}, {'id': 1, 'value': 10}, {'id': 3, 'value': 10}]

💡 Hint

Look at the order of elements with the same 'value' after swapping.

After swapping the first two elements with value 5, the order is changed, showing instability. The output matches option D.

🚀 Application

advanced

Which sorting algorithm to use for large data with limited memory?

You have a very large dataset that cannot fit entirely into memory. You need to sort it efficiently. Which sorting algorithm is best suited for this scenario?

A Quick Sort

B Merge Sort

C Bubble Sort

D Insertion Sort

💡 Hint

Consider external sorting and how the algorithm handles data in chunks.

Merge Sort is suitable for external sorting because it can sort data in chunks and merge them efficiently, even when data doesn't fit in memory.

🧠 Conceptual

expert

Why is stability important in multi-level sorting?

When sorting data by multiple keys (like first by age, then by name), why is it important to use a stable sorting algorithm?

A Because stable sort ensures the order of the first key is preserved when sorting by the second key

B Because stable sort sorts all keys simultaneously in one pass

C Because stable sort always sorts faster than unstable sort

D Because stable sort uses less memory than unstable sort

💡 Hint

Think about sorting by one key, then sorting again by another key without losing previous order.

Stable sort preserves the order of equal elements, so when sorting by the second key, the order from the first key remains intact, enabling correct multi-level sorting.

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