Sorting Stability and When to Use Which Sort in DSA Go

Mental Model

Stable sorting keeps equal items in the same order they started. Different sorts work best for different situations.

Analogy: Imagine sorting playing cards by number but keeping the order of cards with the same number as they were originally laid out on the table.

Unsorted list:
5a -> 3 -> 5b -> 2 -> 3 -> null

'a' and 'b' show two different 5s to track order.

Dry Run Walkthrough

Input: list: 5a -> 3 -> 5b -> 2 -> 3, sort ascending stable

Goal: Sort the list so numbers are in order, but 5a stays before 5b and the first 3 stays before the second 3

Step 1: compare 5a and 3, swap because 3 < 5a

3 -> 5a -> 5b -> 2 -> 3 -> null

Why: We start sorting by moving smaller values forward

Step 2: compare 5a and 5b, no swap because values equal and stable sort keeps order

3 -> 5a -> 5b -> 2 -> 3 -> null

Why: Stable sort keeps original order for equal values

Step 3: compare 5b and 2, swap because 2 < 5b

3 -> 5a -> 2 -> 5b -> 3 -> null

Why: Smaller value moves forward

Step 4: compare 5b and 3, swap because 3 < 5b

3 -> 5a -> 2 -> 3 -> 5b -> null

Why: Smaller value moves forward

Step 5: compare 3 and 5a, swap because 3 < 5a

3 -> 2 -> 3 -> 5a -> 5b -> null

Why: Smaller value moves forward

Step 6: compare 3 and 2, swap because 2 < 3

2 -> 3 -> 3 -> 5a -> 5b -> null

Why: Smaller value moves forward

Result:

2 -> 3 -> 3 -> 5a -> 5b -> null
Order of equal values (3 and 5) is preserved

Annotated Code

DSA Go

package main

import (
	"fmt"
)

type Node struct {
	value int
	label string
	next  *Node
}

// printList prints the linked list values and labels
func printList(head *Node) {
	for curr := head; curr != nil; curr = curr.next {
		fmt.Printf("%d%s", curr.value, curr.label)
		if curr.next != nil {
			fmt.Print(" -> ")
		}
	}
	fmt.Println(" -> null")
}

// stableSort performs a stable insertion sort on linked list
func stableSort(head *Node) *Node {
	if head == nil || head.next == nil {
		return head
	}

	dummy := &Node{value: 0, label: ""} // dummy head for sorted list
	dummy.next = head
	curr := head.next
	head.next = nil

	for curr != nil {
		next := curr.next
		pos := dummy

		// find position to insert curr
		for pos.next != nil && pos.next.value < curr.value {
			pos = pos.next
		}

		// insert curr after pos
		curr.next = pos.next
		pos.next = curr

		curr = next
	}

	return dummy.next
}

func main() {
	// create list: 5a -> 3 -> 5b -> 2 -> 3
	n5b := &Node{value: 5, label: "b", next: nil}
	n3b := &Node{value: 3, label: "", next: n5b}
	n2 := &Node{value: 2, label: "", next: n3b}
	n5a := &Node{value: 5, label: "a", next: n2}
	n3a := &Node{value: 3, label: "", next: n5a}

	head := n3a

	fmt.Print("Original list: ")
	printList(head)

	head = stableSort(head)

	fmt.Print("Sorted list:   ")
	printList(head)
}

for pos.next != nil && pos.next.value < curr.value { pos = pos.next }

find insertion position keeping order for equal values

curr.next = pos.next; pos.next = curr

insert current node in sorted position

curr = next

advance to next node to sort

Output

Original list: 3 -> 5a -> 2 -> 3 -> 5b -> null

Sorted list:   2 -> 3 -> 3 -> 5a -> 5b -> null

Complexity Analysis

Time: O(n^2) because insertion sort compares and inserts each node in sorted order

Space: O(1) because sorting is done in place without extra arrays

vs Alternative: Stable sorts like insertion or merge keep order but may be slower; unstable sorts like quicksort are faster but can reorder equal items

Edge Cases

empty list

returns nil without error

DSA Go

if head == nil || head.next == nil { return head }

single element list

returns the same single node

DSA Go

if head == nil || head.next == nil { return head }

all elements equal

keeps original order because insertion sort is stable

DSA Go

for pos.next != nil && pos.next.value < curr.value { pos = pos.next }

When to Use This Pattern

When you need to keep the original order of equal items after sorting, look for a stable sort like insertion or merge sort.

Common Mistakes

Mistake: Swapping equal elements during sort and losing original order
Fix: Use stable sorting logic that does not swap equal values, e.g., use < in comparisons to keep order

Summary

Stable sorting keeps equal items in their original order after sorting.

Use stable sorts when order of equal elements matters, like sorting cards or records with keys.

The key is to insert or merge without changing the relative order of equal values.

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