Algorithm Comparison - Learning Module

Loading content...

0/276

Stability Considerations

The Subtle Art of Stability

In the sorting algorithm landscape, we've discussed time complexity (how fast) and space complexity (how much memory). Now we turn to a subtler property that often goes unnoticed until it matters critically: stability.

Stability determines whether equal elements retain their original relative order after sorting. This sounds abstract, but its practical implications are profound. Multi-key sorting, database operations, animation sequencing, and data pipeline integrity all depend on understanding stability.

This page provides complete coverage of stability—what it means, why it matters, which algorithms have it, and how to reason about it in real-world scenarios.

What You Will Learn

By the end of this page, you will understand: (1) the precise definition of sorting stability, (2) practical scenarios where stability is essential, (3) which algorithms are stable and why, (4) how to achieve stability when using unstable algorithms, and (5) the relationship between stability, space, and time trade-offs.

What Is Sorting Stability?

Formal Definition:

A sorting algorithm is stable if, for any two elements with equal keys, their relative order in the output matches their relative order in the input.

Mathematically: If a[i] and a[j] have equal sort keys and i < j in the input, then a[i] appears before a[j] in the output.

Concrete Example:

Consider sorting these students by grade (ignoring name):

Input:  [(Alice, 90), (Bob, 85), (Carol, 90), (David, 85)]

Alice and Carol both have grade 90; Bob and David both have grade 85.

Stable sort output:

[(David, 85), (Bob, 85), (Alice, 90), (Carol, 90)]

Wait—this doesn't look right. Actually:

[(Bob, 85), (David, 85), (Alice, 90), (Carol, 90)]

Bob came before David in input (both 85s), so Bob comes before David in output. Alice came before Carol in input (both 90s), so Alice comes before Carol in output.

Unstable sort might output:

[(David, 85), (Bob, 85), (Alice, 90), (Carol, 90)]  — David and Bob swapped!
[(Bob, 85), (David, 85), (Carol, 90), (Alice, 90)]  — Carol and Alice swapped!

Stability Only Matters for Equal Keys

Stability is irrelevant when all keys are unique. It only affects elements that compare as equal. If you're sorting integers with no duplicates, stability doesn't matter. If you're sorting records with potentially duplicate sort keys, stability may be critical.

Why Stability Matters: Real-World Scenarios

Stability isn't just a theoretical property—it has crucial practical applications. Here are the key scenarios where stability determines correctness:

Critical Stability Scenarios

•Multi-Key Sorting (Primary Use Case): Sorting by multiple criteria sequentially. Sort by secondary key first, then by primary key. Stability ensures secondary ordering is preserved within primary groups.
•Database Query Results: When ORDER BY uses columns with duplicate values, users expect consistent ordering. SQL databases use stable sorts to maintain predictable result order.
•Spreadsheet Operations: Users sort tables by one column, then another. Each subsequent sort should preserve the previous ordering for equal values.
•Animation Rendering: Objects with equal z-index should render in their original layer order. Unstable sorting could cause visual flickering.
•Data Pipeline Integrity: ETL processes that sort data multiple times need stability to ensure deterministic, reproducible outputs.

The Multi-Key Sorting Pattern:

This is the most important application of stability. Suppose you have employee records and want to sort by:

Department (primary key)
Salary within department (secondary key)

With a stable sort, you can:

First sort by salary (secondary key)
Then sort by department (primary key) — stability preserves salary order within each department

Example:

Input: [(Alice, Sales, 70k), (Bob, Eng, 80k), (Carol, Sales, 90k), (David, Eng, 60k)]

Step 1: Sort by salary
[(David, Eng, 60k), (Alice, Sales, 70k), (Bob, Eng, 80k), (Carol, Sales, 90k)]

Step 2: Stable sort by department
[(David, Eng, 60k), (Bob, Eng, 80k), (Alice, Sales, 70k), (Carol, Sales, 90k)]

Within Engineering: David (60k) before Bob (80k) — salary order preserved! Within Sales: Alice (70k) before Carol (90k) — salary order preserved!

Unstable Sort Breaks Multi-Key Sorting

If step 2 used an unstable sort, it might output [(Bob, Eng, 80k), (David, Eng, 60k), ...], destroying the salary ordering within Engineering. The secondary sort becomes meaningless. This is why stability is not optional for multi-key sorting—it's a correctness requirement.

Stability Analysis by Algorithm

Let's systematically examine each algorithm to understand whether it's stable and why:

Sorting Algorithm Stability Summary
Algorithm	Stable?	Reason	Can Be Made Stable?
Bubble Sort	Yes	Only swaps adjacent elements when strictly greater	Inherently stable
Selection Sort	No	Swaps with minimum can jump over equal elements	Yes, with linked list
Insertion Sort	Yes	Shifts only when strictly greater, preserving equal order	Inherently stable
Merge Sort	Yes	Merge gives priority to left subarray for equal elements	Inherently stable
Quick Sort	No	Partitioning swaps elements across pivot, changing order	Yes, but loses in-place property
Heap Sort	No	Heap operations don't preserve original positions	Very difficult
Counting Sort	Yes	Placing in reverse order preserves original sequence	Inherently stable
Radix Sort	Yes	Uses stable counting sort as subroutine	Inherently stable

The Stable Algorithm Pattern

Notice that stable algorithms share a common trait: they never swap (or move) equal elements past each other. Bubble Sort compares adjacent pairs but only swaps when strictly greater. Insertion Sort shifts elements but stops when it finds an equal or smaller element. Merge Sort takes from the left when elements are equal. This deliberate design choice creates stability.

Understanding Stable Algorithms

Let's examine exactly why each stable algorithm maintains order among equal elements:

Why Bubble Sort is Stable:

Bubble Sort only compares adjacent elements: arr[j] and arr[j+1].

Critical design choice: Swap only when arr[j] > arr[j+1] (strictly greater).

If arr[j] == arr[j+1], no swap occurs. The element that was earlier stays earlier.

Stability Proof:

Consider two equal elements at positions i and j where i < j.

They can only become adjacent through swaps
When adjacent, arr[i] is at position, arr[j] is at position+1
Since arr[i] == arr[j], no swap occurs
arr[i] remains before arr[j]

The key is the strict > comparison. Using >= would break stability.

bubble-sort-stability.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Bubble Sort - Stable
function bubbleSortStable(arr) {
    const n = arr.length;
    for (let i = 0; i < n - 1; i++) {
        for (let j = 0; j < n - 1 - i; j++) {
            // CRITICAL: Use > not >=
            // Equal elements are NOT swapped, preserving order
            if (arr[j] > arr[j + 1]) {  // Strict greater-than
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
            }
        }
    }
    return arr;
}
 
// If we changed to >=, stability breaks:
// if (arr[j] >= arr[j + 1])  // UNSTABLE VERSION!

Understanding Unstable Algorithms

Now let's examine why certain algorithms are unstable and what specifically causes them to lose stability:

Why Selection Sort is Unstable:

Selection Sort finds the minimum and swaps it with the current position.

The Problem: The swap can jump over equal elements.

Example:

Input: [3a, 2, 3b, 1]   (3a and 3b are equal, a < b in original order)

Pass 1: Find minimum (1), swap with position 0
        [1, 2, 3b, 3a]   ← 3a jumped over 3b!

Pass 2: Find minimum (2), already in place
        [1, 2, 3b, 3a]

Final:  [1, 2, 3b, 3a]   ← 3b appears before 3a — UNSTABLE!

The swap operation is the culprit—it moves elements non-locally.

Can Selection Sort Be Made Stable?

Yes, if using a linked list: instead of swapping, remove the minimum node and insert it at the current position. This takes O(1) for linked list operations and preserves stability. However, for arrays, making Selection Sort stable requires O(n) shifts per element, degrading to O(n²) shifts total—not the O(n) swaps that make Selection Sort interesting.

The Stability-Space Trade-off

A fascinating pattern emerges when we examine stability alongside space complexity:

No O(n log n) algorithm is simultaneously:

Stable
In-place (O(1) auxiliary space)
Comparison-based

This is sometimes called the sorting trilemma—you can have any two, but not all three.

The Sorting Trilemma: Pick Any Two
Algorithm	O(n log n)?	Stable?	In-Place?	Properties Achieved
Merge Sort	Yes ✓	Yes ✓	No ✗	Fast + Stable
Quick Sort	Yes ✓	No ✗	Yes ✓	Fast + In-Place
Heap Sort	Yes ✓	No ✗	Yes ✓	Fast + In-Place
Insertion Sort	No (O(n²)) ✗	Yes ✓	Yes ✓	Stable + In-Place

Why This Trade-off Exists:

Stability requires order tracking: To preserve relative order, an algorithm must somehow 'remember' original positions.

In-place operations are positionally destructive: When you swap elements in place, you destroy positional information unless you explicitly store it elsewhere.

The O(n log n) divide-and-conquer structure: Recursive splitting and merging naturally moves elements far from their original positions. Either you use extra space to track (Merge Sort) or you lose stability (Quick Sort/Heap Sort).

Practical Implication:

When you need stability and O(n log n) time, accept Merge Sort's O(n) space cost—it's the natural consequence of the trade-off. If space is critical and stability dispensable, use Quick Sort or Heap Sort.

Breaking the Trilemma with Non-Comparison Sorts

Counting Sort and Radix Sort are stable and O(n), but require O(n + k) space and only work on specific data types. They 'break' the trilemma by stepping outside the comparison-sort model—another example of how constraints enable different trade-offs.

Techniques for Adding Stability

Sometimes you must use an unstable algorithm but need stable behavior. Several techniques can add stability at various costs:

Stability Augmentation Techniques

•Index Augmentation: Pair each element with its original index. Sort by (key, index) tuples. Equally-keyed elements sort by original position. Cost: O(n) extra space for indices, slightly higher comparison overhead.
•Key Transformation: If keys are numeric, transform to (key * n + index). This ensures unique keys while preserving relative order for equal original keys. Only works if new keys don't overflow.
•Post-Sort Restoration: Not practical—requires knowing which elements were equal and their original order, essentially requiring a second stable sort.
•Algorithm Substitution: Often the simplest solution—use a stable algorithm (Merge Sort) instead of adding stability to an unstable one.

stable-sort-wrapper.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// Making any sort stable via index augmentation
function stableSort(arr, compareFn = (a, b) => a - b) {
    // Create tuples of (value, originalIndex)
    const indexed = arr.map((value, index) => ({ value, index }));
    
    // Sort using augmented comparison:
    // If values equal, compare by original index
    indexed.sort((a, b) => {
        const keyComparison = compareFn(a.value, b.value);
        if (keyComparison !== 0) return keyComparison;
        return a.index - b.index;  // Tiebreaker: original order
    });
    
    // Extract values (indices no longer needed)
    return indexed.map(item => item.value);
}
 
// Usage:
const data = [{name: 'Alice', grade: 90}, {name: 'Bob', grade: 85}, 
              {name: 'Carol', grade: 90}, {name: 'David', grade: 85}];
 
const stableSorted = stableSort(data, (a, b) => a.grade - b.grade);
// Result: Bob(85), David(85), Alice(90), Carol(90)
// Original order preserved within equal grades!

Stability in Standard Libraries

Different languages and runtimes make different stability guarantees. Knowing your library's behavior is essential:

Standard Library Sorting Stability
Language/Library	Function	Stable?	Algorithm Used
JavaScript (Modern)	Array.sort()	Yes ✓	Timsort (hybrid)
Python	sorted() / list.sort()	Yes ✓	Timsort
Java	Arrays.sort() (Objects)	Yes ✓	Timsort / Merge Sort
Java	Arrays.sort() (primitives)	No ✗	Dual-Pivot Quick Sort
C++	std::sort()	No ✗	Introsort (Quick + Heap)
C++	std::stable_sort()	Yes ✓	Merge Sort
Go	sort.Sort()	No ✗	Pattern-defeating quicksort
Go	sort.Stable()	Yes ✓	Merge Sort
Rust	slice.sort()	No ✗	Timsort variant (but unstable)
Rust	slice.sort_stable()	Yes ✓	Merge Sort

Java's Dual Behavior

Java uses different algorithms for primitives vs. objects. Arrays.sort(int[]) uses unstable Dual-Pivot Quick Sort for speed. Arrays.sort(Object[]) uses stable Merge Sort because objects might have meaningful identity beyond value. This design reflects common use cases: primitives rarely need stability, objects often do.

Historical Note: JavaScript's Evolution

Before ECMAScript 2019, JavaScript's Array.sort() had no stability guarantee. Different browsers used different algorithms—V8 used unstable Quick Sort, SpiderMonkey used merge sort. As of ES2019, stability is mandated by the specification. If supporting older environments, explicitly add stability via index augmentation.

Practical Advice:

Check your language/version documentation — Stability guarantees vary and may change between versions
Use explicit stable_sort when available — In C++, Go, Rust, use the explicitly stable variant if you need it
Don't assume — Even if a library happens to be stable, if it's not guaranteed, future versions might change
Test with equal elements — The only way to verify stability is testing with duplicate keys

Summary: Stability Mastery

This page has provided comprehensive coverage of sorting stability. Let's consolidate the essential insights:

Key Takeaways

•Stability means equal elements keep their relative order — Only relevant when duplicates exist in the sort key
•Multi-key sorting requires stability — Sort by secondary key first, then primary; stability preserves secondary order within primary groups
•Stable algorithms: Bubble, Insertion, Merge, Counting, Radix — They achieve stability through careful comparison/placement ordering
•Unstable algorithms: Selection, Quick Sort, Heap Sort — Swaps or structure destroy original position information
•The sorting trilemma — No O(n log n) algorithm is stable, in-place, and comparison-based simultaneously
•Stability can be added — Index augmentation makes any sort stable at O(n) space cost
•Know your library — Stability guarantees vary by language, version, and specific function used

What's next:

We've now covered the three major dimensions of algorithm comparison: time, space, and stability. The final page brings everything together into a practical decision framework—a systematic approach to choosing the right sorting algorithm for any scenario.

Page Complete

You now have deep understanding of sorting stability—what it means, why it matters, which algorithms have it, and how to add it when needed. This knowledge is essential for multi-key sorting, database operations, and any scenario where relative order of equal elements carries meaning. Next, we'll synthesize all dimensions into a practical selection framework.

Stability Considerations

The Subtle Art of Stability

This page provides complete coverage of stability—what it means, why it matters, which algorithms have it, and how to reason about it in real-world scenarios.

What You Will Learn

What Is Sorting Stability?

Formal Definition:

A sorting algorithm is stable if, for any two elements with equal keys, their relative order in the output matches their relative order in the input.

Mathematically: If a[i] and a[j] have equal sort keys and i < j in the input, then a[i] appears before a[j] in the output.

Concrete Example:

Consider sorting these students by grade (ignoring name):

Input:  [(Alice, 90), (Bob, 85), (Carol, 90), (David, 85)]

Alice and Carol both have grade 90; Bob and David both have grade 85.

Stable sort output:

[(David, 85), (Bob, 85), (Alice, 90), (Carol, 90)]

Wait—this doesn't look right. Actually:

[(Bob, 85), (David, 85), (Alice, 90), (Carol, 90)]

Bob came before David in input (both 85s), so Bob comes before David in output. Alice came before Carol in input (both 90s), so Alice comes before Carol in output.

Unstable sort might output:

[(David, 85), (Bob, 85), (Alice, 90), (Carol, 90)]  — David and Bob swapped!
[(Bob, 85), (David, 85), (Carol, 90), (Alice, 90)]  — Carol and Alice swapped!

Stability Only Matters for Equal Keys

Why Stability Matters: Real-World Scenarios

Stability isn't just a theoretical property—it has crucial practical applications. Here are the key scenarios where stability determines correctness:

Critical Stability Scenarios

•Multi-Key Sorting (Primary Use Case): Sorting by multiple criteria sequentially. Sort by secondary key first, then by primary key. Stability ensures secondary ordering is preserved within primary groups.
•Database Query Results: When ORDER BY uses columns with duplicate values, users expect consistent ordering. SQL databases use stable sorts to maintain predictable result order.
•Spreadsheet Operations: Users sort tables by one column, then another. Each subsequent sort should preserve the previous ordering for equal values.
•Animation Rendering: Objects with equal z-index should render in their original layer order. Unstable sorting could cause visual flickering.
•Data Pipeline Integrity: ETL processes that sort data multiple times need stability to ensure deterministic, reproducible outputs.

The Multi-Key Sorting Pattern:

This is the most important application of stability. Suppose you have employee records and want to sort by:

Department (primary key)
Salary within department (secondary key)

With a stable sort, you can:

First sort by salary (secondary key)
Then sort by department (primary key) — stability preserves salary order within each department

Example:

Input: [(Alice, Sales, 70k), (Bob, Eng, 80k), (Carol, Sales, 90k), (David, Eng, 60k)]

Step 1: Sort by salary
[(David, Eng, 60k), (Alice, Sales, 70k), (Bob, Eng, 80k), (Carol, Sales, 90k)]

Step 2: Stable sort by department
[(David, Eng, 60k), (Bob, Eng, 80k), (Alice, Sales, 70k), (Carol, Sales, 90k)]

Within Engineering: David (60k) before Bob (80k) — salary order preserved! Within Sales: Alice (70k) before Carol (90k) — salary order preserved!

Unstable Sort Breaks Multi-Key Sorting

Stability Analysis by Algorithm

Let's systematically examine each algorithm to understand whether it's stable and why:

Sorting Algorithm Stability Summary
Algorithm	Stable?	Reason	Can Be Made Stable?
Bubble Sort	Yes	Only swaps adjacent elements when strictly greater	Inherently stable
Selection Sort	No	Swaps with minimum can jump over equal elements	Yes, with linked list
Insertion Sort	Yes	Shifts only when strictly greater, preserving equal order	Inherently stable
Merge Sort	Yes	Merge gives priority to left subarray for equal elements	Inherently stable
Quick Sort	No	Partitioning swaps elements across pivot, changing order	Yes, but loses in-place property
Heap Sort	No	Heap operations don't preserve original positions	Very difficult
Counting Sort	Yes	Placing in reverse order preserves original sequence	Inherently stable
Radix Sort	Yes	Uses stable counting sort as subroutine	Inherently stable

The Stable Algorithm Pattern

Understanding Stable Algorithms

Let's examine exactly why each stable algorithm maintains order among equal elements:

Why Bubble Sort is Stable:

Bubble Sort only compares adjacent elements: arr[j] and arr[j+1].

Critical design choice: Swap only when arr[j] > arr[j+1] (strictly greater).

If arr[j] == arr[j+1], no swap occurs. The element that was earlier stays earlier.

Stability Proof:

Consider two equal elements at positions i and j where i < j.

They can only become adjacent through swaps
When adjacent, arr[i] is at position, arr[j] is at position+1
Since arr[i] == arr[j], no swap occurs
arr[i] remains before arr[j]

The key is the strict > comparison. Using >= would break stability.

bubble-sort-stability.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Bubble Sort - Stable
function bubbleSortStable(arr) {
    const n = arr.length;
    for (let i = 0; i < n - 1; i++) {
        for (let j = 0; j < n - 1 - i; j++) {
            // CRITICAL: Use > not >=
            // Equal elements are NOT swapped, preserving order
            if (arr[j] > arr[j + 1]) {  // Strict greater-than
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
            }
        }
    }
    return arr;
}
 
// If we changed to >=, stability breaks:
// if (arr[j] >= arr[j + 1])  // UNSTABLE VERSION!

Understanding Unstable Algorithms

Now let's examine why certain algorithms are unstable and what specifically causes them to lose stability:

Why Selection Sort is Unstable:

Selection Sort finds the minimum and swaps it with the current position.

The Problem: The swap can jump over equal elements.

Example:

Input: [3a, 2, 3b, 1]   (3a and 3b are equal, a < b in original order)

Pass 1: Find minimum (1), swap with position 0
        [1, 2, 3b, 3a]   ← 3a jumped over 3b!

Pass 2: Find minimum (2), already in place
        [1, 2, 3b, 3a]

Final:  [1, 2, 3b, 3a]   ← 3b appears before 3a — UNSTABLE!

The swap operation is the culprit—it moves elements non-locally.

Can Selection Sort Be Made Stable?

The Stability-Space Trade-off

A fascinating pattern emerges when we examine stability alongside space complexity:

No O(n log n) algorithm is simultaneously:

Stable
In-place (O(1) auxiliary space)
Comparison-based

This is sometimes called the sorting trilemma—you can have any two, but not all three.

The Sorting Trilemma: Pick Any Two
Algorithm	O(n log n)?	Stable?	In-Place?	Properties Achieved
Merge Sort	Yes ✓	Yes ✓	No ✗	Fast + Stable
Quick Sort	Yes ✓	No ✗	Yes ✓	Fast + In-Place
Heap Sort	Yes ✓	No ✗	Yes ✓	Fast + In-Place
Insertion Sort	No (O(n²)) ✗	Yes ✓	Yes ✓	Stable + In-Place

Why This Trade-off Exists:

Stability requires order tracking: To preserve relative order, an algorithm must somehow 'remember' original positions.

In-place operations are positionally destructive: When you swap elements in place, you destroy positional information unless you explicitly store it elsewhere.

Practical Implication:

Breaking the Trilemma with Non-Comparison Sorts

Techniques for Adding Stability

Sometimes you must use an unstable algorithm but need stable behavior. Several techniques can add stability at various costs:

Stability Augmentation Techniques

•Index Augmentation: Pair each element with its original index. Sort by (key, index) tuples. Equally-keyed elements sort by original position. Cost: O(n) extra space for indices, slightly higher comparison overhead.
•Key Transformation: If keys are numeric, transform to (key * n + index). This ensures unique keys while preserving relative order for equal original keys. Only works if new keys don't overflow.
•Post-Sort Restoration: Not practical—requires knowing which elements were equal and their original order, essentially requiring a second stable sort.
•Algorithm Substitution: Often the simplest solution—use a stable algorithm (Merge Sort) instead of adding stability to an unstable one.

stable-sort-wrapper.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// Making any sort stable via index augmentation
function stableSort(arr, compareFn = (a, b) => a - b) {
    // Create tuples of (value, originalIndex)
    const indexed = arr.map((value, index) => ({ value, index }));
    
    // Sort using augmented comparison:
    // If values equal, compare by original index
    indexed.sort((a, b) => {
        const keyComparison = compareFn(a.value, b.value);
        if (keyComparison !== 0) return keyComparison;
        return a.index - b.index;  // Tiebreaker: original order
    });
    
    // Extract values (indices no longer needed)
    return indexed.map(item => item.value);
}
 
// Usage:
const data = [{name: 'Alice', grade: 90}, {name: 'Bob', grade: 85}, 
              {name: 'Carol', grade: 90}, {name: 'David', grade: 85}];
 
const stableSorted = stableSort(data, (a, b) => a.grade - b.grade);
// Result: Bob(85), David(85), Alice(90), Carol(90)
// Original order preserved within equal grades!

Stability in Standard Libraries

Different languages and runtimes make different stability guarantees. Knowing your library's behavior is essential:

Standard Library Sorting Stability
Language/Library	Function	Stable?	Algorithm Used
JavaScript (Modern)	Array.sort()	Yes ✓	Timsort (hybrid)
Python	sorted() / list.sort()	Yes ✓	Timsort
Java	Arrays.sort() (Objects)	Yes ✓	Timsort / Merge Sort
Java	Arrays.sort() (primitives)	No ✗	Dual-Pivot Quick Sort
C++	std::sort()	No ✗	Introsort (Quick + Heap)
C++	std::stable_sort()	Yes ✓	Merge Sort
Go	sort.Sort()	No ✗	Pattern-defeating quicksort
Go	sort.Stable()	Yes ✓	Merge Sort
Rust	slice.sort()	No ✗	Timsort variant (but unstable)
Rust	slice.sort_stable()	Yes ✓	Merge Sort

Java's Dual Behavior

Historical Note: JavaScript's Evolution

Practical Advice:

Check your language/version documentation — Stability guarantees vary and may change between versions
Use explicit stable_sort when available — In C++, Go, Rust, use the explicitly stable variant if you need it
Don't assume — Even if a library happens to be stable, if it's not guaranteed, future versions might change
Test with equal elements — The only way to verify stability is testing with duplicate keys

Summary: Stability Mastery

This page has provided comprehensive coverage of sorting stability. Let's consolidate the essential insights:

Key Takeaways

•Stability means equal elements keep their relative order — Only relevant when duplicates exist in the sort key
•Multi-key sorting requires stability — Sort by secondary key first, then primary; stability preserves secondary order within primary groups
•Stable algorithms: Bubble, Insertion, Merge, Counting, Radix — They achieve stability through careful comparison/placement ordering
•Unstable algorithms: Selection, Quick Sort, Heap Sort — Swaps or structure destroy original position information
•The sorting trilemma — No O(n log n) algorithm is stable, in-place, and comparison-based simultaneously
•Stability can be added — Index augmentation makes any sort stable at O(n) space cost
•Know your library — Stability guarantees vary by language, version, and specific function used

What's next:

Page Complete