Sorting Stability and When to Use Which Sort in DSA Go - 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 Go

arr := []int{4, 2, 4, 3}
// Stable sort preserves order of equal elements
stableSort(arr)
// Unstable sort may reorder equal elements
unstableSort(arr)

This code sorts an array twice: once with a stable sort and once with an unstable sort, showing the difference in order of equal elements.

Execution Table

Step	Operation	Array State	Stability Effect	Visual State
1	Start with array	[4a, 2, 4b, 3]	N/A	[4a, 2, 4b, 3] (4a and 4b are distinct elements with same value)
2	Apply stable sort (Merge Sort)	[2, 3, 4a, 4b]	Preserves order of 4a before 4b	[2, 3, 4a, 4b]
3	Reset to original array	[4a, 2, 4b, 3]	N/A	[4a, 2, 4b, 3]
4	Apply unstable sort (Quick Sort)	[2, 3, 4b, 4a]	May reorder 4a and 4b	[2, 3, 4b, 4a]
5	End	[2, 3, 4b, 4a]	Stability lost	[2, 3, 4b, 4a]

💡 Sorting completes; stable sort keeps original order of equal elements, unstable sort may not.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
arr	[4a, 2, 4b, 3]	[2, 3, 4a, 4b]	[4a, 2, 4b, 3]	[2, 3, 4b, 4a]	[2, 3, 4b, 4a]

Key Moments - 3 Insights

Why does stable sort keep 4a before 4b but unstable sort does not?

Stable sort algorithms keep equal elements in their original order as shown in step 2, while unstable sorts like quick sort may reorder them as seen in step 4.

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

Choose stable sort when the order of equal elements matters, for example when sorting by multiple criteria. This is shown in the decision step in the concept flow.

Does unstable sort always reorder equal elements?

No, unstable sort may sometimes keep order by chance, but it does not guarantee it. Step 4 shows a case where order changes.

Visual Quiz - 3 Questions

Look at the execution table, what is the array state after applying stable sort?

A [2, 3, 4a, 4b]

B [2, 3, 4b, 4a]

C [4a, 2, 4b, 3]

D [3, 2, 4a, 4b]

💡 Hint

Check row 2 in the execution_table where stable sort is applied.

At which step does the unstable sort reorder equal elements?

A Step 2

B Step 3

C Step 4

D Step 1

💡 Hint

Look at the array state changes in step 4 in the execution_table.

If stability is not required, which sorting algorithm is recommended according to the concept flow?

A Insertion Sort

B Quick Sort

C Merge Sort

D Bubble Sort

💡 Hint

Refer to the decision branch in the concept_flow diagram.

Concept Snapshot

Sorting Stability:
- Stable sort keeps equal elements in original order.
- Unstable sort may reorder equal elements.
When to use:
- Use stable sort if order of equal elements matters.
- Use unstable sort for faster average performance if order doesn't matter.

Full Transcript

This visual execution shows how sorting stability affects the order of equal elements. Starting with an array containing two equal values labeled 4a and 4b, stable sort keeps 4a before 4b after sorting, while unstable sort may swap their order. The concept flow guides choosing stable sorts like merge or insertion when order matters, and unstable sorts like quick sort when speed is preferred and order does not matter. The execution table traces each step, showing array states and stability effects. Key moments clarify common confusions about stability and usage. The quiz tests understanding by referencing these visuals.

Practice

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

easy

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

B. It sorts elements faster than any other algorithm

C. It uses less memory than unstable sorts

D. It only works on numbers, not strings

Solution

1. Step 1: Understand stability in sorting

   A stable sort keeps the relative order of items that compare equal the same as before sorting.

2. Step 2: Compare options

   Only It keeps the original order of equal elements after sorting describes this property correctly. Other options describe speed, memory, or data type restrictions, which are unrelated to stability.

3. Final Answer:

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

4. Quick Check:

   Stable sort = keeps equal items order [OK]

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

Common Mistakes:

• Confusing stability with speed
• Thinking stability means less memory use
• Believing stability depends on data type

2. Which of the following Go code snippets correctly uses the sort.SliceStable function to sort a slice of structs by an integer field Age?

easy

A. sort.SliceStable(people, func(i, j int) bool { return people[i].Age > people[j].Age })

B. sort.Slice(people, func(i, j int) bool { return people[i].Age > people[j].Age })

C. sort.Slice(people, func(i, j int) bool { return people[i].Age < people[j].Age })

D. sort.SliceStable(people, func(i, j int) bool { return people[i].Age < people[j].Age })

Solution

1. Step 1: Identify stable sort usage

   The question asks for stable sorting by Age ascending. sort.SliceStable is the stable function.

2. Step 2: Check comparison function

   The comparison must be people[i].Age < people[j].Age for ascending order.

3. Final Answer:

   sort.SliceStable(people, func(i, j int) bool { return people[i].Age < people[j].Age }) -> Option D

4. Quick Check:

   Stable + ascending = sort.SliceStable(people, func(i, j int) bool { return people[i].Age < people[j].Age }) [OK]

Hint: Use SliceStable with less-than for ascending stable sort [OK]

Common Mistakes:

• Using sort.Slice instead of sort.SliceStable
• Reversing comparison for ascending order
• Mixing stable and unstable sort functions

3. Given the following Go code, what will be the output after sorting?

type Item struct {
  Name string
  Rank int
}

items := []Item{{"A", 2}, {"B", 1}, {"C", 2}}
sort.Slice(items, func(i, j int) bool { return items[i].Rank < items[j].Rank })
for _, item := range items {
  fmt.Print(item.Name, " ")
}

medium

A. A C B

B. B A C

C. B C A

D. C A B

Solution

1. Step 1: Understand sorting criteria

   The slice is sorted by Rank ascending using sort.Slice, which is unstable.

2. Step 2: Analyze order of equal Rank elements

   Items with Rank 2 are "A" and "C". Since sort.Slice is unstable, their relative order may change. The output shows "B" first (Rank 1), then "C", then "A".

3. Final Answer:

   B C A -> Option C

4. Quick Check:

   Unstable sort may change equal items order [OK]

Hint: Unstable sort may reorder equal keys; check output carefully [OK]

Common Mistakes:

• Assuming stable order with sort.Slice
• Mixing up item names and ranks
• Ignoring unstable sort behavior

4. The following Go code attempts to sort a slice of strings stably by length but does not work as expected. What is the error?

words := []string{"cat", "bat", "apple", "dog"}
sort.Slice(words, func(i, j int) bool { return len(words[i]) < len(words[j]) })

medium

A. Using sort.Slice instead of sort.SliceStable causes unstable sort

B. The comparison function should use > instead of <

C. The slice must be converted to []struct before sorting

D. The code is correct and stable by default

Solution

1. Step 1: Identify sorting function used

   The code uses sort.Slice, which is unstable.

2. Step 2: Understand stability requirement

   To sort stably by length, sort.SliceStable must be used instead.

3. Final Answer:

   Using sort.Slice instead of sort.SliceStable causes unstable sort -> Option A

4. Quick Check:

   Stable sort requires SliceStable, not Slice [OK]

Hint: Use SliceStable for stable sorting, not Slice [OK]

Common Mistakes:

• Thinking comparison direction affects stability
• Believing slice type conversion is needed
• Assuming sort.Slice is stable

5. You have a list of employees with fields Name and Department. You want to sort them first by Department alphabetically and then by Name alphabetically within each department, preserving the order of employees with the same name. Which sorting approach is best in Go?

hard

A. Use one unstable sort by Department only

B. Use two stable sorts: first by Name, then by Department

C. Use one stable sort by concatenated Department+Name string

D. Use two unstable sorts: first by Department, then by Name

Solution

1. Step 1: Understand multi-level sorting with stability

   To sort by Department then Name, stable sorts allow sorting by the secondary key first, then primary key.

2. Step 2: Apply stable sorts in correct order

   Sort first by Name (secondary key) stably, then by Department (primary key) stably. This preserves Name order within Departments.

3. Final Answer:

   Use two stable sorts: first by Name, then by Department -> Option B

4. Quick Check:

   Two stable sorts in reverse order = correct multi-level sort [OK]

Hint: Sort by secondary key first, then primary key with stable sorts [OK]

Common Mistakes:

• Using unstable sorts causing order loss
• Sorting primary key first losing secondary order
• Trying one sort on combined keys without stability