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

↓

Compare elements

↓

Decide to swap or not

↓

Maintain relative order if stable?

↓

Repeat until sorted

↓

Sorted array with stability info

↓

Use case decision based on stability, speed, memory

Shows how sorting algorithms process elements, maintain order if stable, and guide which sort to use based on needs.

Execution Sample

DSA C#

int[] arr = {4, 2, 3, 2, 1};
// Using Stable Sort (Insertion Sort)
for (int i = 1; i < arr.Length; i++) {
  int key = arr[i];
  int j = i - 1;
  while (j >= 0 && arr[j] > key) {
    arr[j + 1] = arr[j]; j--;
  }
  arr[j + 1] = key;
}

Insertion sort keeps the relative order of equal elements while sorting the array.

Execution Table

Step	Operation	Array State	Pointer Changes	Visual State
1	Start with array	[4, 2, 3, 2, 1]	i=1, key=2, j=0	4 -> 2 -> 3 -> 2 -> 1
2	Compare arr[j]=4 > key=2	No change yet	j=0 -> j=-1 after shift	4 -> 4 -> 3 -> 2 -> 1 (shift 4 right)
3	Insert key=2 at j+1=0	[2, 4, 3, 2, 1]	i=2, key=3, j=1	2 -> 4 -> 3 -> 2 -> 1
4	Compare arr[j]=4 > key=3	No change yet	j=1 -> j=0 after shift	2 -> 4 -> 4 -> 2 -> 1 (shift 4 right)
5	Insert key=3 at j+1=1	[2, 3, 4, 2, 1]	i=3, key=2, j=2	2 -> 3 -> 4 -> 2 -> 1
6	Compare arr[j]=4 > key=2	No change yet	j=2 -> j=1 after shift	2 -> 3 -> 4 -> 4 -> 1 (shift 4 right)
7	Compare arr[j]=3 > key=2	No change yet	j=1 -> j=0 after shift	2 -> 3 -> 3 -> 4 -> 1 (shift 3 right)
8	Insert key=2 at j+1=1	[2, 2, 3, 4, 1]	i=4, key=1, j=3	2 -> 2 -> 3 -> 4 -> 1
9	Compare arr[j]=4 > key=1	No change yet	j=3 -> j=2 after shift	2 -> 2 -> 3 -> 4 -> 4 (shift 4 right)
10	Compare arr[j]=3 > key=1	No change yet	j=2 -> j=1 after shift	2 -> 2 -> 3 -> 3 -> 4 (shift 3 right)
11	Compare arr[j]=2 > key=1	No change yet	j=1 -> j=0 after shift	2 -> 2 -> 2 -> 3 -> 4 (shift 2 right)
12	Compare arr[j]=2 > key=1	No change yet	j=0 -> j=-1 after shift	2 -> 2 -> 2 -> 3 -> 4 (shift 2 right)
13	Insert key=1 at j+1=0	[1, 2, 2, 3, 4]	Sorting complete	1 -> 2 -> 2 -> 3 -> 4

💡 i reaches array length, sorting complete with stable order preserved

Variable Tracker

Variable	Start	After Step 1	After Step 5	After Step 8	Final
i	1	2	3	4	5 (end)
key	2	3	2	1	N/A
j	0	-1	0	0	N/A
Array	[4,2,3,2,1]	[2,4,3,2,1]	[2,3,4,2,1]	[2,2,3,4,1]	[1,2,2,3,4]

Key Moments - 3 Insights

Why does insertion sort keep the relative order of equal elements?

Because it only shifts elements greater than the key, not equal ones, so equal elements stay in original order (see steps 5-8 in execution_table).

What happens if the sorting algorithm is unstable?

Equal elements might swap places, changing their original order, which can cause issues when sorting complex data with keys (not shown in this stable example).

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

Choose stable sorts when you need to preserve the order of equal elements, such as sorting by multiple criteria step-by-step.

Visual Quiz - 3 Questions

Look at the execution_table at step 8, what is the array state?

A [2, 2, 3, 4, 1]

B [2, 3, 4, 2, 1]

C [2, 2, 4, 3, 1]

D [4, 2, 3, 2, 1]

💡 Hint

Check the 'Array State' column at step 8 in execution_table

At which step does the key=1 get inserted into the array?

A Step 10

B Step 13

C Step 12

D Step 9

💡 Hint

Look for the step where 'Insert key=1' is mentioned in execution_table

If the sort was unstable, what could happen to the two '2's in the array?

A They would remain in the same order

B One would be removed

C They might swap places

D They would both move to the end

💡 Hint

Refer to key_moments about stable vs unstable sorting

Concept Snapshot

Sorting Stability:
- Stable sort keeps equal elements in original order.
- Unstable sort may reorder equal elements.
When to use:
- Use stable sort when order matters (e.g., multi-key sorting).
- Use unstable sort for speed or memory if order doesn't matter.
Examples: Insertion sort (stable), Quick sort (unstable).

Full Transcript

This visual trace shows how a stable sorting algorithm like insertion sort processes an array step-by-step. It compares elements, shifts larger ones right, and inserts the key in the correct place without changing the order of equal elements. The variable tracker shows how pointers and the array change after key steps. Key moments clarify why stability matters and when to choose stable or unstable sorts. The quiz tests understanding of array states and stability effects during sorting.

Practice

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

easy

A. It uses less memory than unstable sorts.

B. It sorts elements in ascending order only.

C. It keeps the original order of equal elements unchanged.

D. It always sorts in place without extra space.

Solution

1. Step 1: Understand stability in sorting

   A stable sort means if two elements are equal, their order stays the same as before sorting.

2. Step 2: Compare with other options

   Options B, C, and D describe other properties but not stability.

3. Final Answer:

   It keeps the original order of equal elements unchanged. -> Option C

4. Quick Check:

   Stable sort = keeps equal elements order [OK]

Hint: Stable means equal items keep their 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 is the correct C# syntax to call the built-in stable sort method on a list named numbers?

easy

A. Sort(numbers);

B. numbers.Sort();

C. numbers.StableSort();

D. numbers.OrderBy(x => x);

Solution

1. Step 1: Identify the correct method for sorting a List in C#

   The List<T> class has a Sort() method that sorts the list in place and is stable.

2. Step 2: Check other options

   Sort(numbers); is incorrect syntax as Sort is an instance method. numbers.OrderBy(x => x); returns an IEnumerable but does not sort the list in place. numbers.StableSort(); is not a valid method in C#.

3. Final Answer:

   numbers.Sort(); -> Option B

4. Quick Check:

   List.Sort() is correct stable sort call [OK]

Hint: Use List.Sort() to sort in place stably [OK]

Common Mistakes:

• Using LINQ OrderBy without assignment
• Assuming StableSort() exists
• Calling Sort as a standalone function

3. Consider the following C# code snippet:

var items = new List<(int id, string name)> {
  (1, "apple"),
  (2, "banana"),
  (3, "apple"),
  (4, "banana")
};
items = items.OrderBy(item => item.name).ToList();
foreach(var item in items) {
  Console.Write(item.id + " ");
}

What is the output?

medium

A. 1 3 2 4

B. 3 1 2 4

C. 2 4 1 3

D. 4 2 3 1

Solution

1. Step 1: Understand sorting by name with stability

   The list is sorted by the 'name' field. Since OrderBy is stable, equal names keep their original order.

2. Step 2: Trace the sorted order

   Names sorted alphabetically: "apple", "apple", "banana", "banana". Original order for "apple" is id 1 then 3; for "banana" is id 2 then 4.

3. Final Answer:

   1 3 2 4 -> Option A

4. Quick Check:

   Stable sort keeps equal names order: 1 3 2 4 [OK]

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

Common Mistakes:

• Assuming unstable sort changes order of equal names
• Mixing up id order after sorting
• Ignoring stability property of OrderBy

4. You wrote this code to sort a list of strings by length but it does not keep the original order of equal length strings:

var words = new List<string> { "cat", "dog", "bat", "apple" };
words.Sort((a, b) => a.Length.CompareTo(b.Length));

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

medium

A. The Sort method is unstable for custom comparers.

B. The comparison function is incorrect.

C. The list contains duplicates.

D. Strings cannot be sorted by length.

Solution

1. Step 1: Understand stability with custom comparers

   In C#, List.Sort with a custom comparer is not guaranteed to be stable, so equal keys may reorder.

2. Step 2: Check other options

   The comparison function is correct, duplicates do not affect stability, and strings can be sorted by length.

3. Final Answer:

   The Sort method is unstable for custom comparers. -> Option A

4. Quick Check:

   Custom comparer Sort is unstable [OK]

Hint: Custom comparer Sort may be unstable [OK]

Common Mistakes:

• Blaming comparison function for instability
• Thinking duplicates cause instability
• Assuming all Sort calls are stable

5. You have a list of employee records with id and department. You want to sort employees by department alphabetically but keep the original order of employees within the same department. Which sorting approach is best?

hard

A. Use an unstable sort by department for faster sorting.

B. Sort by department descending to keep order.

C. Sort by id first, then sort by department using unstable sort.

D. Use a stable sort by department to keep original order within groups.

Solution

1. Step 1: Identify requirement to keep original order within same department

   This means sorting must be stable so equal departments keep their original order.

2. Step 2: Evaluate options

   Using an unstable sort by department loses original order within groups. Using a stable sort by department preserves it. Sorting by id first then by department with an unstable sort does not guarantee preservation. Sorting descending does not address stability.

3. Final Answer:

   Use a stable sort by department to keep original order within groups. -> Option D

4. Quick Check:

   Stable sort keeps order within equal keys [OK]

Hint: Stable sort preserves order within equal keys [OK]

Common Mistakes:

• Using unstable sort and losing order
• Sorting by id after department breaks order
• Sorting descending does not preserve order