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
Test your understanding
Look at the execution table at step 3, what happens when two equal elements are compared in stable sort?
AThey are swapped to change order
BOne element is removed
CThey keep their original order
DSorting 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?
AStep 10
BStep 5
CStep 7
DStep 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?
AIt would say 'Order may change' for all steps
BStability effect would be irrelevant
CIt would say 'Order preserved' for all steps
DSorting 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.