Sorting Stability and When to Use Which Sort in DSA Python

Mental Model

Stable sorting keeps equal items in the same order as before. Different sorts work best in different situations.

Analogy: Imagine sorting playing cards by number but keeping the order of cards with the same number as they were in your hand.

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

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

Dry Run Walkthrough

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

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

Step 1: Start sorting with stable sort (like merge sort)

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

Why: We want to keep order of equal numbers while sorting

Step 2: Split list into halves: left=5a -> 3 -> 5b, right=2 -> 3

Left: 5a -> 3 -> 5b -> null
Right: 2 -> 3 -> null

Why: Divide to conquer smaller parts

Step 3: Sort left half stably: 3 -> 5a -> 5b

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

Why: 3 is smallest, 5a before 5b keeps original order

Step 4: Sort right half stably: 2 -> 3

2 -> 3 -> null

Why: 2 is smaller than 3, order kept

Step 5: Merge sorted halves stably: 2 -> 3 -> 3 -> 5a -> 5b

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

Why: Equal 3s keep their order, 5a before 5b preserved

Result:

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

Annotated Code

DSA Python

class Node:
    def __init__(self, val, label=None):
        self.val = val
        self.label = label  # to track duplicates
        self.next = None

def print_list(head):
    curr = head
    result = []
    while curr:
        if curr.label:
            result.append(f"{curr.val}{curr.label}")
        else:
            result.append(str(curr.val))
        curr = curr.next
    print(" -> ".join(result) + " -> null")

def merge_sorted_lists(l1, l2):
    dummy = Node(0)
    tail = dummy
    while l1 and l2:
        if l1.val < l2.val:
            tail.next = l1
            l1 = l1.next
        elif l1.val > l2.val:
            tail.next = l2
            l2 = l2.next
        else:  # equal values, keep order from l1 then l2
            tail.next = l1
            l1 = l1.next
        tail = tail.next
    tail.next = l1 if l1 else l2
    return dummy.next

def merge_sort(head):
    if not head or not head.next:
        return head
    # find middle
    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    mid = slow.next
    slow.next = None
    left = merge_sort(head)
    right = merge_sort(mid)
    return merge_sorted_lists(left, right)

# Driver code
# Create list: 5a -> 3 -> 5b -> 2 -> 3
n1 = Node(5, 'a')
n2 = Node(3)
n3 = Node(5, 'b')
n4 = Node(2)
n5 = Node(3)
n1.next = n2
n2.next = n3
n3.next = n4
n4.next = n5

print("Original list:")
print_list(n1)
sorted_head = merge_sort(n1)
print("Sorted list (stable):")
print_list(sorted_head)

if not head or not head.next: return head

base case: list with 0 or 1 node is already sorted

slow, fast = head, head.next while fast and fast.next: slow = slow.next fast = fast.next.next

find middle node to split list into halves

mid = slow.next slow.next = None

split list into two halves

left = merge_sort(head) right = merge_sort(mid)

recursively sort left and right halves

while l1 and l2: if l1.val < l2.val: tail.next = l1 l1 = l1.next elif l1.val > l2.val: tail.next = l2 l2 = l2.next else: tail.next = l1 l1 = l1.next tail = tail.next

merge two sorted lists keeping order of equal values from left list first

Output

Original list:

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

Sorted list (stable):

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

Complexity Analysis

Time: O(n log n) because merge sort divides list and merges in linear time per level

Space: O(log n) due to recursion stack in merge sort

vs Alternative: Stable sorts like merge sort keep order of equal items, unlike quicksort which is usually unstable but faster on average

Edge Cases

empty list

returns None immediately without error

DSA Python

if not head or not head.next:
    return head

single element list

returns the single node as sorted

DSA Python

if not head or not head.next:
    return head

all elements equal

keeps original order of nodes

DSA Python

else:
    tail.next = l1
    l1 = l1.next

When to Use This Pattern

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

Common Mistakes

Mistake: Using an unstable sort when stability is required, causing order of duplicates to change
Fix: Choose a stable sorting algorithm like merge sort or insertion sort

Summary

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

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

The key insight is that stable sorts merge or insert equal elements without changing their relative order.

Practice

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

easy

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

B. It sorts the elements in ascending order only.

C. It uses less memory than unstable sorts.

D. It always sorts in place without extra space.

Solution

1. Step 1: Understand stability in sorting

   A stable sort keeps elements with the same value in the same order as they appeared originally.

2. Step 2: Compare options with definition

   Only It keeps the original order of equal elements unchanged. describes this property correctly. Other options describe different concepts.

3. Final Answer:

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

4. Quick Check:

   Stable sort = keeps order of equal elements [OK]

Hint: Stable means equal items keep their original 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 Python sorting methods is stable by default?

easy

A. sorted() function

B. list.sort() method

C. Neither sorted() nor list.sort()

D. Both sorted() and list.sort()

Solution

1. Step 1: Recall Python sorting stability

   Both sorted() and list.sort() use Timsort, which is stable.

2. Step 2: Check options

   Options A and B are each correct alone, but Both sorted() and list.sort() correctly states both are stable.

3. Final Answer:

   Both sorted() and list.sort() -> Option D

4. Quick Check:

   Python sorts are stable by default [OK]

Hint: Python's built-in sorts are stable by default [OK]

Common Mistakes:

• Thinking only one method is stable
• Confusing stability with sorting order
• Assuming custom sorts are stable by default

3. Consider this list of tuples representing (name, score):

data = [("Alice", 90), ("Bob", 90), ("Charlie", 85)]

What will be the output after sorting by score using sorted(data, key=lambda x: x[1])?

medium

A. [('Charlie', 85), ('Bob', 90), ('Alice', 90)]

B. [('Alice', 90), ('Bob', 90), ('Charlie', 85)]

C. [('Charlie', 85), ('Alice', 90), ('Bob', 90)]

D. [('Bob', 90), ('Alice', 90), ('Charlie', 85)]

Solution

1. Step 1: Understand sorting by score

   The sort uses the second item (score) as key, sorting ascending: 85, 90, 90.

2. Step 2: Check stability for equal scores

   Since Python's sort is stable, 'Alice' and 'Bob' keep their original order for score 90.

3. Final Answer:

   [('Charlie', 85), ('Alice', 90), ('Bob', 90)] -> Option C

4. Quick Check:

   Stable sort keeps 'Alice' before 'Bob' [OK]

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

Common Mistakes:

• Swapping order of equal elements
• Sorting descending by mistake
• Ignoring stability property

4. You wrote this code to sort a list of dictionaries by 'age':

people = [{'name': 'Ann', 'age': 25}, {'name': 'Ben', 'age': 20}, {'name': 'Cara', 'age': 25}]
people.sort(key=lambda x: x['age'])
print(people)

But the output does not keep the original order of people with the same age. What is the likely cause?

medium

A. The key function is incorrect.

B. The dictionaries are unordered, causing instability.

C. The list.sort() method is stable, so no cause.

D. The sort method used is unstable.

Solution

1. Step 1: Recall Python sort stability

   Python's list.sort() is stable, so it keeps order of equal keys.

2. Step 2: Understand dictionary order

   Before Python 3.7, dictionaries did not preserve insertion order, so printing may show different order.

3. Step 3: Identify cause

   If using older Python or unordered dicts, the printed order may seem unstable even if sort is stable.

4. Final Answer:

   The dictionaries are unordered, causing instability. -> Option B

5. Quick Check:

   Unordered dicts can hide stable sort [OK]

Hint: Unordered dicts can hide stable sort effects [OK]

Common Mistakes:

• Blaming sort method instead of dict order
• Changing key function unnecessarily
• Ignoring Python version differences

5. You have a list of student records with (name, grade, age). You want to sort by grade ascending, then by age descending, but keep the original order for students with same grade and age. Which sorting approach is best?

hard

A. Use a stable sort twice: first by age descending, then by grade ascending.

B. Use an unstable sort once with a combined key (grade, -age).

C. Use a stable sort once with key (grade, age).

D. Sort by age ascending, then by grade descending using stable sorts.

Solution

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

   To sort by multiple keys and keep original order for ties, use stable sorts starting from the last key.

2. Step 2: Apply sorting order

   First sort by age descending (second key), then by grade ascending (first key), both stable.

3. Step 3: Check options

   Use a stable sort twice: first by age descending, then by grade ascending. matches this approach. Others either use unstable sort or wrong key order.

4. Final Answer:

   Use a stable sort twice: first by age descending, then by grade ascending. -> Option A

5. Quick Check:

   Stable sorts chained preserve multi-key order [OK]

Hint: Sort by last key first with stable sort, then first key [OK]

Common Mistakes:

• Sorting keys in wrong order
• Using unstable sort for multi-key sorting
• Ignoring descending order for age