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

Concept Flow - Sorting Stability and When to Use Which Sort

Start with unsorted array

↓

Choose sorting algorithm

↓

Check if stable needed?

Yes→Use stable sort

↓

Use unstable sort

↓

Sort array

↓

Sorted array with stability info

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

Execution Sample

DSA Javascript

const arr = [{val:5, id:'a'}, {val:3, id:'b'}, {val:5, id:'c'}];
// Stable sort by val ascending
arr.sort((x,y) => x.val - y.val);
console.log(arr);

Sorts an array of objects by 'val' using a stable sort to keep order of equal elements.

Execution Table

Step	Operation	Array State	Comparison	Swap?	Stability Effect
1	Compare index 0 and 1	[{5,a}, {3,b}, {5,c}]	5 vs 3	Yes	No impact yet
2	Swap index 0 and 1	[{3,b}, {5,a}, {5,c}]	-	Yes	No impact yet
3	Compare index 1 and 2	[{3,b}, {5,a}, {5,c}]	5 vs 5	No	Equal values keep order (stable)
4	Final sorted array	[{3,b}, {5,a}, {5,c}]	-	-	Order of equal 5's preserved
5	End	-	-	-	Sorting complete with stability

💡 All elements compared and sorted; stability preserved for equal values.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
arr	[{5,a}, {3,b}, {5,c}]	[{3,b}, {5,a}, {5,c}]	[{3,b}, {5,a}, {5,c}]	[{3,b}, {5,a}, {5,c}]	[{3,b}, {5,a}, {5,c}]

Key Moments - 3 Insights

Why does the order of equal elements (val=5) stay the same after sorting?

Because the sort used is stable, it does not swap equal elements, preserving their original order as shown in step 3 and 4 of the execution_table.

What happens if we use an unstable sort on this array?

Unstable sort might swap equal elements, changing their original order, which can be seen by comparing the 'Swap?' and 'Stability Effect' columns in the execution_table.

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

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

Visual Quiz - 3 Questions

Look at the execution_table, what is the array state after step 2?

A [{3,b}, {5,a}, {5,c}]

B [{5,a}, {3,b}, {5,c}]

C [{5,c}, {3,b}, {5,a}]

D [{3,b}, {5,c}, {5,a}]

💡 Hint

Check the 'Array State' column at step 2 in the execution_table.

At which step does the sort confirm stability by not swapping equal elements?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look at the 'Swap?' and 'Stability Effect' columns for step 3 in the execution_table.

If the array had unique values only, how would the stability effect change?

A Stability would reverse the array

B Stability would not matter as no equal elements exist

C Stability would cause more swaps

D Stability would break the sort

💡 Hint

Refer to the 'Stability Effect' column and think about equal elements role.

Concept Snapshot

Sorting Stability:
- Stable sort keeps order of equal elements.
- Unstable sort may reorder equal elements.
When to use:
- Use stable sort if order of equal items matters.
- Use unstable sort for speed if order doesn't matter.
Examples: Merge sort (stable), Quick sort (unstable).

Full Transcript

This visual trace shows sorting an array of objects by their 'val' property using a stable sort. The array starts as [{5,a}, {3,b}, {5,c}]. Step 1 compares first two elements and swaps because 5 > 3. Step 2 shows the array after swap: [{3,b}, {5,a}, {5,c}]. Step 3 compares equal values 5 and 5 and does not swap, preserving their original order, demonstrating stability. The final sorted array is [{3,b}, {5,a}, {5,c}]. Stability is important when equal elements must keep their relative order, such as sorting by multiple criteria. Unstable sorts may reorder equal elements, which can be faster but loses this order. Choose stable sorts like merge sort when order matters, and unstable sorts like quick sort when speed is priority and order doesn't matter.

Practice

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

easy

A. It keeps the original order of equal elements after sorting

B. It sorts elements faster than unstable algorithms

C. It uses less memory than unstable algorithms

D. It always sorts in ascending order

Solution

1. Step 1: Understand stability in sorting

   A stable sort keeps the relative order of items with equal keys unchanged.

2. Step 2: Compare with other options

   Speed, memory use, or sorting order do not define stability.

3. Final Answer:

   It keeps the original order of equal elements after sorting -> Option A

4. Quick Check:

   Stable sort = keeps equal elements order [OK]

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

Common Mistakes:

• Confusing stability with speed
• Thinking stability means sorting ascending only
• Assuming stable sorts use less memory

2. Which of the following is the correct way to call JavaScript's built-in sort method to sort numbers in ascending order?

easy

A. arr.sort()

B. arr.sort((a, b) => a + b)

C. arr.sort((a, b) => b - a)

D. arr.sort((a, b) => a - b)

Solution

1. Step 1: Understand JavaScript's default sort

   By default, arr.sort() sorts elements as strings, not numbers.

2. Step 2: Use compare function for numeric ascending

   The compare function (a, b) => a - b sorts numbers ascending correctly.

3. Final Answer:

   arr.sort((a, b) => a - b) -> Option D

4. Quick Check:

   Numeric ascending sort uses (a, b) => a - b [OK]

Hint: Use (a, b) => a - b for ascending numeric sort [OK]

Common Mistakes:

• Using arr.sort() alone for numbers
• Using (a, b) => b - a for ascending order
• Using (a, b) => a + b which is invalid

3. Consider the array of objects:

const items = [
  {name: 'apple', price: 50},
  {name: 'banana', price: 20},
  {name: 'cherry', price: 50},
  {name: 'date', price: 20}
];
items.sort((a, b) => a.price - b.price);

What will be the order of items after sorting?

medium

A. [{banana,20}, {date,20}, {cherry,50}, {apple,50}]

B. [{date,20}, {banana,20}, {cherry,50}, {apple,50}]

C. [{banana,20}, {date,20}, {apple,50}, {cherry,50}]

D. [{date,20}, {banana,20}, {apple,50}, {cherry,50}]

Solution

1. Step 1: Understand the sort comparator

   The comparator sorts by price ascending: 20 then 50.

2. Step 2: Check stability of JavaScript sort

   JavaScript's sort is stable in modern engines, so equal price items keep original order.

3. Step 3: Apply stability to equal price items

   For price 20, original order is banana then date; for 50, apple then cherry.

4. Final Answer:

   [{banana,20}, {date,20}, {apple,50}, {cherry,50}] -> Option C

5. Quick Check:

   Stable sort keeps equal price order [OK]

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

Common Mistakes:

• Assuming unstable sort changes order of equal items
• Mixing up banana and date order
• Ignoring stability of JavaScript sort

4. The following code tries to sort an array of strings by length, which may not keep the original order of equal length strings:

const arr = ['bat', 'cat', 'apple', 'dog'];
arr.sort((a, b) => a.length - b.length);

What is the main reason the original order of equal length strings might not be preserved?

medium

A. Strings cannot be sorted by length

B. JavaScript's sort is unstable in some engines

C. The comparator function is incorrect

D. The array contains duplicates

Solution

1. Step 1: Check comparator correctness

   The comparator (a, b) => a.length - b.length correctly compares string lengths.

2. Step 2: Understand JavaScript sort stability

   JavaScript's sort is stable in modern engines but may be unstable in older engines, causing order change.

3. Final Answer:

   JavaScript's sort is unstable in some engines -> Option B

4. Quick Check:

   Unstable sort breaks equal element order [OK]

Hint: Old JS engines have unstable sort, losing order [OK]

Common Mistakes:

• Blaming comparator function
• Thinking strings can't be sorted by length
• Assuming duplicates cause instability

5. You have a list of student records with name and score. You want to sort by score ascending but keep the original order for students with the same score. Which sorting algorithm should you choose and why?

hard

A. MergeSort, because it is stable and sorts efficiently

B. QuickSort, because it is fast but unstable

C. HeapSort, because it uses less memory

D. BubbleSort, because it is simple and stable

Solution

1. Step 1: Identify need for stability

   We want to keep original order for equal scores, so stability is required.

2. Step 2: Choose algorithm with stability and efficiency

   MergeSort is stable and efficient (O(n log n)), suitable for this task.

3. Step 3: Compare other options

   QuickSort is fast but unstable; HeapSort is unstable; BubbleSort is stable but inefficient.

4. Final Answer:

   MergeSort, because it is stable and sorts efficiently -> Option A

5. Quick Check:

   Stable + efficient = MergeSort [OK]

Hint: Stable and efficient sort for equal keys: MergeSort [OK]

Common Mistakes:

• Choosing QuickSort ignoring instability
• Picking BubbleSort despite inefficiency
• Confusing HeapSort as stable