Sorting Stability and When to Use Which Sort in DSA Rust

Mental Model

Sorting stability means keeping the original order of equal items after sorting. Different sorts work best in different situations depending on data size and order.

Analogy: Imagine sorting a deck of cards by number but keeping the same order for cards with the same number, like keeping friends standing in line without mixing them up.

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

Stable sort keeps order of equal items:
2 -> 3 -> 3 -> 5a -> 5b -> null

Unstable sort may change order:
2 -> 3 -> 3 -> 5b -> 5a -> null

Dry Run Walkthrough

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

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

Step 1: Compare first two items 5a and 3, swap because 3 < 5a

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

Why: We want smaller numbers first

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

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

Why: Stable sort keeps original order of equal items

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

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

Why: Smaller number moves forward

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

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

Why: Smaller number moves forward

Step 5: Repeat passes until fully sorted with stable order

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

Why: Final sorted list with original equal order preserved

Result:

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

Annotated Code

DSA Rust

use std::fmt::{Display, Formatter, Result};

#[derive(Clone)]
struct Item {
    value: i32,
    label: char, // to distinguish equal values
}

impl Display for Item {
    fn fmt(&self, f: &mut Formatter<'_>) -> Result {
        write!(f, "{}{}", self.value, self.label)
    }
}

fn stable_sort(items: &mut Vec<Item>) {
    let n = items.len();
    for i in 0..n {
        for j in 0..n - i - 1 {
            // Compare adjacent items
            if items[j].value > items[j + 1].value {
                items.swap(j, j + 1); // swap if out of order
            }
            // if equal, do not swap to keep stability
        }
    }
}

fn main() {
    let mut items = vec![
        Item { value: 5, label: 'a' },
        Item { value: 3, label: 'a' },
        Item { value: 5, label: 'b' },
        Item { value: 2, label: 'a' },
        Item { value: 3, label: 'b' },
    ];

    stable_sort(&mut items);

    for item in items {
        print!("{} -> ", item);
    }
    print!("null\n");
}

if items[j].value > items[j + 1].value {

compare adjacent items to decide if swap needed

items.swap(j, j + 1);

swap only if next item is smaller to keep order

Output

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

Complexity Analysis

Time: O(n^2) because bubble sort compares pairs repeatedly over the list

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

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

Edge Cases

empty list

no sorting needed, list remains empty

DSA Rust

let n = items.len(); for i in 0..n { ... } handles zero length

all items equal

no swaps happen, original order preserved

DSA Rust

if items[j].value > items[j + 1].value { ... } skips swap on equal

single item list

no sorting needed, list remains same

DSA Rust

for loops run zero times if n < 2

When to Use This Pattern

When a problem requires sorting but keeping the original order of equal elements, reach for a stable sort like bubble or merge sort because it preserves order while sorting.

Common Mistakes

Mistake: Swapping equal items which breaks stability
Fix: Only swap when the next item is strictly smaller, not equal

Summary

Stable sorting keeps the original order of equal items after sorting.

Use stable sorts when order of equal elements matters, like sorting by multiple keys.

The key is to swap only when strictly out of order to preserve stability.

Practice

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

easy

A. It uses less memory than unstable sorts

B. It sorts elements in ascending order only

C. It always runs faster than unstable sorts

D. It keeps the original order of equal elements unchanged

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 options with definition

   Only It keeps the original order of equal elements unchanged matches this meaning. Other options describe unrelated properties.

3. Final Answer:

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

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 faster sorting
• Assuming stability means less memory use

2. Which Rust standard library method sorts a slice with a stable sort without requiring a comparator closure?

easy

A. slice.sort_unstable_by()

B. slice.sort_unstable()

C. slice.sort()

D. slice.sort_by()

Solution

1. Step 1: Recall Rust slice sorting methods

   Rust's slice.sort() uses a stable sorting algorithm.

2. Step 2: Differentiate stable and unstable methods

   sort_unstable() and sort_unstable_by() are unstable sorts. sort_by() is stable but requires a comparator.

3. Final Answer:

   slice.sort() -> Option C

4. Quick Check:

   slice.sort() = stable sort [OK]

Hint: Use sort() for stable sorting in Rust [OK]

Common Mistakes:

• Choosing sort_unstable() thinking it's stable
• Confusing sort_by() with unstable sort
• Not knowing sort() is stable by default

3. Given the Rust code below, what is the output?

let mut data = [(3, 'a'), (1, 'b'), (3, 'c'), (2, 'd')];
data.sort();
println!("{:?}", data);

medium

A. [(1, 'b'), (2, 'd'), (3, 'a'), (3, 'c')]

B. [(1, 'b'), (2, 'd'), (3, 'c'), (3, 'a')]

C. [(3, 'a'), (3, 'c'), (2, 'd'), (1, 'b')]

D. [(2, 'd'), (1, 'b'), (3, 'a'), (3, 'c')]

Solution

1. Step 1: Understand sorting of tuples in Rust

   Rust sorts tuples by first element, then second if first are equal. Here, sorting by integer first.

2. Step 2: Apply stable sort to keep order of equal keys

   Elements with key 3 are (3, 'a') then (3, 'c'). Stable sort keeps this order.

3. Final Answer:

   [(1, 'b'), (2, 'd'), (3, 'a'), (3, 'c')] -> Option A

4. Quick Check:

   Stable sort keeps (3, 'a') before (3, 'c') [OK]

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

Common Mistakes:

• Swapping order of equal keys
• Ignoring tuple sorting rules
• Assuming unstable sort by default

4. The following Rust code uses sort_unstable() but the order of equal elements is important. What is the main issue?

let mut items = [(2, 'x'), (1, 'y'), (2, 'z')];
items.sort_unstable();
println!("{:?}", items);

medium

A. The code will not compile because sort_unstable() requires a comparator

B. The order of (2, 'x') and (2, 'z') may change, breaking stability

C. The code will panic at runtime due to unstable sort

D. The output will always be sorted and stable

Solution

1. Step 1: Understand sort_unstable() behavior

   sort_unstable() sorts faster but does not guarantee stable order of equal elements.

2. Step 2: Identify problem with equal keys

   Elements with key 2 may swap order, so (2, 'x') and (2, 'z') order can change, which breaks stability.

3. Final Answer:

   The order of (2, 'x') and (2, 'z') may change, breaking stability -> Option B

4. Quick Check:

   Unstable sort = order of equal keys can change [OK]

Hint: Unstable sort can reorder equal elements [OK]

Common Mistakes:

• Thinking unstable sort always panics
• Assuming unstable sort requires comparator
• Believing unstable sort keeps order

5. You have a list of student records with fields (score: i32, name: &str). You want to sort by score ascending but keep the original order of students with the same score. Which sorting method should you use in Rust and why?

hard

A. Use sort() because it is stable and preserves order of equal scores

B. Use sort_unstable() because it is faster and order doesn't matter

C. Use sort_unstable_by() with a custom comparator for stability

D. Use sort_by() but it is unstable so order may change

Solution

1. Step 1: Identify requirement for stability

   We want to keep original order of students with same score, so stable sort is needed.

2. Step 2: Choose Rust method that is stable

   sort() is stable and sorts ascending by default. sort_unstable() is faster but unstable. sort_unstable_by() is unstable even with comparator. sort_by() is stable but Use sort_by() but it is unstable so order may change claims it is unstable incorrectly.

3. Final Answer:

   Use sort() because it is stable and preserves order of equal scores -> Option A

4. Quick Check:

   Stable sort needed = use sort() [OK]

Hint: Stable sort keeps order of equal keys; use sort() [OK]

Common Mistakes:

• Choosing unstable sort for speed ignoring order
• Thinking sort_unstable_by() is stable
• Misunderstanding sort_by() stability