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

Concept Flow - Sorting Stability and When to Use Which Sort

Start with unsorted array

↓

Choose sorting algorithm

↓

Is stability required?

Yes→Use stable sort (e.g., Merge Sort, Insertion Sort)

↓

Sort preserving order of equal elements

↓

Use unstable sort (e.g., Quick Sort, Heap Sort)

↓

Sort array

↓

Sorted array with or without stability

↓

Done

The flow shows choosing a sorting algorithm based on whether stability is needed, then sorting the array accordingly.

Execution Sample

DSA C++

int arr[] = {4, 2, 4, 3};
// Stable sort preserves order of equal 4s
std::stable_sort(arr, arr+4);
// Unstable sort may reorder equal 4s
std::sort(arr, arr+4);

This code sorts an array with duplicates using stable and unstable sorts to show difference in order preservation.

Execution Table

Step	Operation	Array State	Comparison / Action	Stability Effect
1	Initial array	[4, 2, 4, 3]	N/A	N/A
2	Stable sort: Compare 4 and 2	[4, 2, 4, 3]	4 > 2, swap	Order of equal 4s preserved
3	Stable sort: Compare 4 and 4	[2, 4, 4, 3]	Equal elements, keep order	Order preserved
4	Stable sort: Compare 4 and 3	[2, 4, 4, 3]	4 > 3, swap	Order preserved
5	Stable sort: Final sorted	[2, 3, 4, 4]	N/A	Equal 4s in original order
6	Reset array	[4, 2, 4, 3]	N/A	N/A
7	Unstable sort: Compare 4 and 2	[4, 2, 4, 3]	4 > 2, swap	Order of equal 4s may change
8	Unstable sort: Compare 4 and 4	[2, 4, 4, 3]	Equal elements, may reorder	Order may change
9	Unstable sort: Compare 4 and 3	[2, 4, 4, 3]	4 > 3, swap	Order may change
10	Unstable sort: Final sorted	[2, 3, 4, 4]	N/A	Equal 4s order not guaranteed
11	End	N/A	Sorting complete	N/A

💡 Sorting ends after array is fully sorted; stable sort preserves order of equal elements, unstable may not.

Variable Tracker

Variable	Start	After Stable Sort	Reset	After Unstable Sort	Final
arr	[4, 2, 4, 3]	[2, 3, 4, 4]	[4, 2, 4, 3]	[2, 3, 4, 4]	[2, 3, 4, 4]

Key Moments - 3 Insights

Why does stable sort keep the order of equal elements while unstable sort may not?

Stable sort algorithms like Merge Sort carefully merge elements preserving original order of equals, as shown in steps 3 and 5 where equal 4s keep their order. Unstable sorts like Quick Sort may swap equal elements arbitrarily (steps 8 and 10), changing their order.

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

Choose stable sort when the order of equal elements matters, for example sorting by multiple keys. This is shown in the flow where if stability is required, stable sort is chosen to preserve order (concept_flow).

Does unstable sort always produce a wrong order?

No, unstable sort still sorts correctly by value, but equal elements may appear in any order. The final array is sorted (steps 10), but order of duplicates is not guaranteed.

Visual Quiz - 3 Questions

Look at the execution table at step 3, what happens when two equal elements are compared in stable sort?

A They are swapped to change order

B One element is removed

C They keep their original order

D Sorting stops

💡 Hint

Check 'Comparison / Action' and 'Stability Effect' columns at step 3 in execution_table

At which step does the unstable sort finish sorting the array?

A Step 10

B Step 5

C Step 7

D Step 3

💡 Hint

Look for 'Final sorted' operation under unstable sort in execution_table

If the array had no duplicate elements, how would the stability effect column change?

A It would say 'Order may change' for all steps

B Stability effect would be irrelevant

C It would say 'Order preserved' for all steps

D Sorting would fail

💡 Hint

Consider what stability means when no equal elements exist, check stability effect column in execution_table

Concept Snapshot

Sorting Stability:
- Stable sort keeps original order of equal elements
- Unstable sort may reorder equal elements
When to use:
- Use stable sort if order of duplicates matters
- Use unstable sort for faster average performance
Examples:
- Stable: Merge Sort, Insertion Sort
- Unstable: Quick Sort, Heap Sort

Full Transcript

This visual execution shows how sorting algorithms handle stability. Starting with an array containing duplicates, stable sort preserves the order of equal elements, while unstable sort may reorder them. The execution table traces each comparison and action, highlighting stability effects. Variable tracker shows array states before and after sorts. Key moments clarify why stability matters and when to choose stable or unstable sorts. The quiz tests understanding of stability behavior and sorting completion steps.

Practice

1. Which of the following sorting algorithms is stable by default?

easy

A. Merge Sort

B. Quick Sort

C. Heap Sort

D. Selection Sort

Solution

1. Step 1: Understand stability in sorting

   A stable sort keeps the relative order of equal elements the same as in the input.

2. Step 2: Check common sorting algorithms

   Merge Sort is stable because it merges sorted halves without changing order of equal elements. Quick Sort, Heap Sort, and Selection Sort are not stable by default.

3. Final Answer:

   Merge Sort -> Option A

4. Quick Check:

   Stable sort = Merge Sort [OK]

Hint: Remember: Merge Sort is stable, Quick Sort is not [OK]

Common Mistakes:

• Thinking Quick Sort is stable
• Confusing stability with time complexity
• Assuming all comparison sorts are stable

2. Which syntax correctly declares a stable sort call on a vector v in C++ STL?

easy

A. v.stable_sort();

B. std::sort(v.begin(), v.end(), stable);

C. std::stable_sort(v.begin(), v.end());

D. std::sort_stable(v.begin(), v.end());

Solution

1. Step 1: Recall C++ STL stable sort syntax

   The function is std::stable_sort with two iterators as arguments.

2. Step 2: Check options for correctness

   std::stable_sort(v.begin(), v.end()); matches correct syntax. Options A, B, and D are invalid or do not exist in STL.

3. Final Answer:

   std::stable_sort(v.begin(), v.end()); -> Option C

4. Quick Check:

   Correct stable sort syntax = std::stable_sort(v.begin(), v.end()); [OK]

Hint: Use std::stable_sort with iterators for stable sorting [OK]

Common Mistakes:

• Using std::sort for stable sorting
• Calling non-existent member functions
• Passing wrong arguments to sort functions

3. What is the output of the following C++ code snippet?

struct Item {
  int key;
  char id;
};

std::vector<Item> v = {{2, 'a'}, {1, 'b'}, {2, 'c'}};
std::stable_sort(v.begin(), v.end(), [](Item x, Item y) { return x.key < y.key; });
for (auto &item : v) std::cout << item.key << item.id << ' ';

medium

A. 2c 2a 1b

B. 1b 2c 2a

C. 2a 2c 1b

D. 1b 2a 2c

Solution

1. Step 1: Understand stable_sort behavior

   stable_sort sorts by key ascending but keeps relative order of equal keys.

2. Step 2: Sort vector and trace output

   Keys sorted: 1, 2, 2. For key=2, 'a' comes before 'c' in original, so order stays '2a' then '2c'. Output: "1b 2a 2c "

3. Final Answer:

   1b 2a 2c -> Option D

4. Quick Check:

   Stable sort keeps order of equal keys [OK]

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

Common Mistakes:

• Assuming equal keys reorder arbitrarily
• Confusing stable_sort with sort
• Ignoring the lambda comparator effect

4. Identify the error in this code snippet that tries to use stable sort on an array:

int arr[] = {3, 1, 2};
std::stable_sort(arr, arr + 3);
for (int i = 0; i < 3; i++) std::cout << arr[i] << ' ';

medium

A. No error; code runs correctly

B. Array pointers used incorrectly in stable_sort

C. stable_sort cannot be used on arrays

D. Missing comparator function causes error

Solution

1. Step 1: Check stable_sort usage on arrays

   std::stable_sort accepts pointers as iterators, so arr and arr+3 are valid.

2. Step 2: Verify code correctness

   Code sorts array {3,1,2} to {1,2,3} and prints correctly. No error present.

3. Final Answer:

   No error; code runs correctly -> Option A

4. Quick Check:

   stable_sort works with array pointers [OK]

Hint: stable_sort works with pointers, no comparator needed for default order [OK]

Common Mistakes:

• Thinking stable_sort needs vector only
• Assuming comparator is mandatory
• Confusing pointers with iterators

5. You have a list of employees with fields name and age. You want to sort them by age but keep the original order for employees with the same age. Which sorting algorithm should you use and why?

hard

A. Heap Sort, because it uses less memory

B. Stable Sort (like Merge Sort), to preserve order of equal ages

C. Quick Sort, because it is faster on average

D. Selection Sort, because it is simple to implement

Solution

1. Step 1: Understand requirement for stability

   We want to keep original order for employees with same age, so sorting must be stable.

2. Step 2: Choose sorting algorithm based on stability

   Merge Sort or any stable sort preserves order of equal keys. Quick Sort, Heap Sort, Selection Sort are not stable by default.

3. Final Answer:

   Stable Sort (like Merge Sort), to preserve order of equal ages -> Option B

4. Quick Check:

   Stable sort needed to keep order [OK]

Hint: Use stable sort to keep order of equal keys [OK]

Common Mistakes:

• Choosing faster but unstable sorts
• Ignoring stability requirement
• Confusing simplicity with correctness