Sorting Stability and When to Use Which Sort in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does it mean for a sorting algorithm to be stable?

A stable sorting algorithm keeps the original order of equal elements the same after sorting. For example, if two items have the same value, they stay in the order they appeared before sorting.

beginner

Name a common stable sorting algorithm.

Merge Sort is a common stable sorting algorithm. It keeps equal elements in their original order while sorting.

intermediate

Why might you choose an unstable sort like Quick Sort over a stable one?

Quick Sort is often faster and uses less memory, so you might choose it when speed and memory are more important than keeping the order of equal elements.

beginner

Which sorting algorithm is best for sorting small lists or nearly sorted data?

Insertion Sort is best for small or nearly sorted lists because it is simple and efficient in those cases.

intermediate

What is a key factor to consider when choosing a sorting algorithm?

Consider the size of the data, whether stability is needed, memory limits, and the expected order of data (random, nearly sorted, etc.).

Which sorting algorithm is stable by default?

A Merge Sort

B Quick Sort

C Heap Sort

D Selection Sort

Merge Sort maintains the order of equal elements, making it stable.

Why is stability important in sorting?

A To use less memory

B To sort faster

C To sort in reverse order

D To keep equal elements in their original order

Stability means equal elements keep their original order after sorting.

Which sorting algorithm is usually fastest on average but unstable?

A Bubble Sort

B Quick Sort

C Insertion Sort

D Merge Sort

Quick Sort is fast on average but does not guarantee stability.

For nearly sorted data, which sort is most efficient?

A Insertion Sort

B Heap Sort

C Selection Sort

D Quick Sort

Insertion Sort performs well on nearly sorted data because it minimizes shifts.

Which factor is NOT important when choosing a sorting algorithm?

A Data size

B Stability requirement

C Color of the data

D Memory usage

Color of data is irrelevant to sorting algorithm choice.

Explain what sorting stability means and give an example of when you would need a stable sort.

Think about sorting a list of people by age, then by name.

Describe how you would choose a sorting algorithm based on data size, stability, and data order.

Consider trade-offs between speed, memory, and stability.

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