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.