Sorting Formalization - Learning Module

Loading content...

0/276

Stability — Preserving Relative Order of Equal Elements

The Property That Changes Everything

Among all the properties of sorting algorithms—time complexity, space complexity, adaptivity—stability is uniquely important yet frequently overlooked. It doesn't affect performance, but it fundamentally changes what your sorted output looks like when elements compare as equal.

Consider sorting a list of employees by salary. Two employees earn the same salary: "Alice" was hired first, "Bob" was hired second. After sorting by salary, should Alice still appear before Bob, or can the algorithm put Bob first?

This seemingly minor question has profound implications for:

Multi-key sorting (sort by department, then by salary within department)
Maintaining meaningful original ordering
UI consistency (users expect deterministic behavior)
Database query result reproducibility
Testing and debugging

Understanding stability transforms you from someone who "sorts data" to someone who controls the complete output specification.

Learning Objectives

By the end of this page, you will understand the precise definition of stability, recognize which algorithms are stable (and why), know when stability is essential versus optional, understand how to achieve stable sorting with unstable algorithms, and master multi-key sorting using stability.

Formal Definition of Stability

Definition: Stable Sorting Algorithm

A sorting algorithm is stable if and only if for any two elements aᵢ and aⱼ where i < j (aᵢ appears before aⱼ in the input) and aᵢ = aⱼ (they compare as equal), then in the output, aᵢ still appears before aⱼ.

In mathematical notation:

∀i, j where i < j: if key(aᵢ) = key(aⱼ), then position(aᵢ) < position(aⱼ) in output

Key Insight: Equal by What?

Stability is defined relative to the comparison key, not the complete object identity:

If we sort by salary, two people with the same salary are "equal"
If we sort by age, two people with the same age are "equal"
The complete objects (including name, ID, etc.) may be different

Stability preserves the original relative order of elements that are equal according to the sorting key.

Stability is About Ties

When all elements are distinct (no ties), stability has no visible effect—there's only one correct sorted order. Stability only matters when elements can be equal according to the comparison key. The more ties in your data, the more stability matters.

Visualizing Stability:

Consider sorting cards by value only (ignoring suit):

Input: [5♦, 3♠, 5♣, 3♥]

Stable sort output: [3♠, 3♥, 5♦, 5♣]

3♠ was before 3♥ in input → 3♠ still before 3♥ in output
5♦ was before 5♣ in input → 5♦ still before 5♣ in output

Unstable sort output (one possibility): [3♥, 3♠, 5♣, 5♦]

The 3s and 5s are in some order, but not necessarily the original order

Both outputs are "correctly sorted" by value—an unstable sort doesn't produce wrong results. But a stable sort provides the additional guarantee about tie-breaking.

stability_demo.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
from dataclasses import dataclass
from typing import List
 
@dataclass
class Card:
    value: int  # 1-13 (Ace to King)
    suit: str   # ♠ ♥ ♦ ♣
    
    def __repr__(self):
        values = {1: 'A', 11: 'J', 12: 'Q', 13: 'K'}
        v = values.get(self.value, str(self.value))
        return f"{v}{self.suit}"
 
def is_stable_sort_result(input_arr: List[Card], output_arr: List[Card]) -> bool:
    """
    Verify if the output maintains stability relative to input.
    For each pair of equal-value cards in output, check that their
    relative order matches the input order.
    """
    # Build a map: card -> original position
    original_positions = {id(card): i for i, card in enumerate(input_arr)}
    
    # For each pair of equal-value cards in output, verify order
    for i, card_i in enumerate(output_arr):
        for j, card_j in enumerate(output_arr):
            if i < j and card_i.value == card_j.value:
                # card_i appears before card_j in output
                # Check: was card_i before card_j in input?
                if original_positions[id(card_i)] > original_positions[id(card_j)]:
                    return False  # Order was reversed
    return True
 
# Example with explicit card objects (not just values)
cards = [
    Card(5, '♦'),
    Card(3, '♠'),
    Card(5, '♣'),
    Card(3, '♥')
]
 
print(f"Original: {cards}")
 
# Python's sorted() is STABLE
sorted_stable = sorted(cards, key=lambda c: c.value)
print(f"Stable sort by value: {sorted_stable}")
print(f"Is stable? {is_stable_sort_result(cards, sorted_stable)}")
 
# Simulate an unstable sort (intentionally scramble ties)
import random
sorted_unstable = sorted(cards, key=lambda c: (c.value, random.random()))
print(f"\nSimulated unstable: {sorted_unstable}")
print(f"Is stable? {is_stable_sort_result(cards, sorted_unstable)}")

Why Stability Matters in Practice

Stability isn't just a theoretical property—it has critical practical implications. Here are the key scenarios where stability is essential.

Scenario 1: Multi-Key Sorting via Sequential Sorts

The most important use of stability is enabling multi-key sorting through successive single-key sorts. Here's how it works:

Goal: Sort employees by (department ASC, salary DESC)

Method with stable sort:

First, sort by salary (DESC) — secondary key
Then, sort by department (ASC) — primary key

Because the second sort is stable, employees with the same department retain their relative order from the first sort, which was by salary.

This technique is fundamental and used extensively in database engines.

multi_key_stable.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
from dataclasses import dataclass
from typing import List
 
@dataclass
class Employee:
    name: str
    department: str
    salary: int
    
    def __repr__(self):
        return f"{self.name:8} | {self.department:12} | ${self.salary:,}"
 
employees = [
                                    Employee("Alice", "Engineering", 95000),
                                    Employee("Bob", "Engineering", 85000),
                                    Employee("Charlie", "Engineering", 95000),
                                    Employee("Diana", "Marketing", 75000),
                                    Employee("Eve", "Marketing", 85000),
                                    Employee("Frank", "Sales", 80000),
                                    Employee("Grace", "Sales", 80000),
                                ]
 
print("Original order:")
for e in employees:
                            print(f"  {e}")
 
# STABLE Multi- key sort: department ASC, then salary DESC within department
# Method: Sort by secondary key FIRST, then primary key
 
# Step 1: Sort by salary(descending) - SECONDARY key first
step1 = sorted(employees, key = lambda e: e.salary, reverse = True)
print("\nAfter sorting by salary (DESC) - secondary key:")
for e in step1:
                    print(f"  {e}")
 
# Step 2: Sort by department(ascending) - PRIMARY key
# Because Python's sort is STABLE, same-department employees
# retain their salary order from Step 1
step2 = sorted(step1, key = lambda e: e.department)
print("\nAfter stable sort by department (ASC) - primary key:")
for e in step2:
            print(f"  {e}")
 
# The result: Within each department, employees are ordered by salary DESC!
# This works ONLY because the second sort is STABLE
 
# Compare with direct multi- key sort(also works, but different mechanism)
print("\nVerification with direct multi-key sort:")
direct = sorted(employees, key = lambda e: (e.department, -e.salary))
for e in direct:
        print(f"  {e}")

Scenario 2: Preserving Meaningful Original Order

Sometimes the input order carries meaning—perhaps it represents chronological arrival, user preference ranking, or import sequence. A stable sort preserves this implicit information.

Example: You have a task list ordered by user priority. You want to sort by due date while preserving priority order among tasks due on the same date. Stable sorting by due date maintains the priority order for same-date tasks.

Scenario 3: UI Consistency and User Expectations

Users expect consistent behavior. If they sort a table by column A, then by column B, they expect the same result each time. Unstable sorts may produce different orderings of ties across runs (due to implementation-dependent behavior), confusing users.

Scenario 4: Database and Reproducibility

SQL ORDER BY and Stability

SQL's ORDER BY does NOT guarantee stable sorting! The order of rows with equal sort keys is undefined. To get consistent results, you must add tie-breaker columns: ORDER BY salary DESC, id ASC. Many bugs arise from assuming database ordering is stable when it isn't.

Which Sorting Algorithms Are Stable?

Different sorting algorithms have different stability properties. Some are naturally stable, some are naturally unstable, and some can be made stable with modifications.

Sorting Algorithm Stability Reference
Algorithm	Stable?	Time	Space	Notes
Bubble Sort	✅ Stable	O(n²)	O(1)	Only swap when strictly greater
Insertion Sort	✅ Stable	O(n²)	O(1)	Insert before greater, not before equal
Merge Sort	✅ Stable	O(n log n)	O(n)	Prefer left element when equal in merge
Timsort	✅ Stable	O(n log n)	O(n)	Used in Python, Java; designed for stability
Counting Sort	✅ Stable	O(n + k)	O(k)	Process right-to-left for stability
Radix Sort	✅ Stable	O(dn)	O(n)	Depends on stable subroutine
Quick Sort	❌ Unstable	O(n log n) avg	O(log n)	Partition can reorder equal elements
Heap Sort	❌ Unstable	O(n log n)	O(1)	Heap operations don't preserve order
Selection Sort	❌ Unstable	O(n²)	O(1)	Swapping minimum can skip over equal
Introsort	❌ Unstable	O(n log n)	O(log n)	Uses Quick/Heap which are unstable

Why Is Merge Sort Stable?

In the merge step, when comparing elements from left and right halves:

If left ≤ right, take from left
If left > right, take from right

The key is the "≤" (not "<"). By taking from left when equal, we preserve the original order since left elements came before right elements in the original array.

Why Is Quick Sort Unstable?

During partitioning, elements equal to the pivot can end up on either side depending on their initial positions relative to the partition process. The swapping mechanism doesn't track or preserve original order.

stable_merge.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
def merge_stable(left: list, right: list, key = lambda x: x) -> list:
        """
    Stable merge: When elements are equal, prefer left.
    This preserves original order because left elements
    came before right elements in the array.
    """
    result = []
    i = j = 0
    
    while i < len(left) and j < len(right):
        # KEY INSIGHT: Use <= to prefer left when equal
    if key(left[i]) <= key(right[j]):  # <= makes it stable
    result.append(left[i])
    i += 1
        else:
    result.append(right[j])
    j += 1
 
    result.extend(left[i:])
    result.extend(right[j:])
    return result
 
def merge_unstable(left: list, right: list, key = lambda x: x) -> list:
    """
    Unstable merge: Uses < instead of <=.
    When equal, takes from right, violating stability.
    """
    result = []
    i = j = 0
 
    while i < len(left) and j < len(right):
    if key(left[i]) < key(right[j]):  # < makes it unstable
    result.append(left[i])
    i += 1
        else:
    result.append(right[j])
    j += 1
 
    result.extend(left[i:])
    result.extend(right[j:])
    return result
 
# Demonstrate the difference
from dataclasses import dataclass
 
@dataclass
    class Item:
    key: int
    label: str
    
    def __repr__(self):
    return f"{self.key}:{self.label}"
 
    left = [Item(3, 'A'), Item(5, 'B')]
    right = [Item(3, 'C'), Item(5, 'D')]
 
    print("Left:  ", left)
    print("Right: ", right)
    print()
    print("Stable merge (prefer left when equal):")
    print("  ", merge_stable(left, right, key = lambda x: x.key))
    print()
    print("Unstable merge (prefer right when equal):")
    print("  ", merge_unstable(left, right, key = lambda x: x.key))

Making Unstable Algorithms Stable

Sometimes you need stability but can only use an unstable algorithm (perhaps for performance or library constraints). There are several techniques to achieve stability.

Method 1: Augment Keys with Original Position

The most general technique: pair each element with its original index, sort by (key, index), then extract elements.

This works with ANY sorting algorithm because we've made all keys unique—there are no ties to cause instability.

Trade-off: Extra space for indices, extra comparisons for the secondary key.

stabilize_sort.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
from typing import List, TypeVar, Callable
    import random
 
T = TypeVar('T')
 
def stable_sort_via_augmentation(
        arr: List[T],
        key: Callable[[T], any],
        unstable_sort: Callable[[List[tuple], Callable], List[tuple]]
    ) -> List[T]:
    """
    Make any unstable sort stable by augmenting with original indices.
    
    The augmented key is(original_key, original_index).
    Since indices are unique, there are no ties.
    """
    # Step 1: Augment with original indices
    augmented = [(item, i) for i, item in enumerate(arr)]
    
    # Step 2: Sort using augmented key
    augmented_key = lambda pair: (key(pair[0]), pair[1])
    sorted_augmented = unstable_sort(augmented, augmented_key)
    
    # Step 3: Extract original items
    return [item for item, _ in sorted_augmented]
 
# Example: Simulate unstable Quick Sort behavior
def quick_sort_unstable(arr: List, key = lambda x: x) -> List:
    """Simulate unstable sort (uses random to scramble ties)"""
    return sorted(arr, key = lambda x: (key(x), random.random()))
 
# Data with ties
items = [
        { 'name': 'Alice', 'priority': 1 },
        { 'name': 'Bob', 'priority': 2 },
        { 'name': 'Charlie', 'priority': 1 },
        { 'name': 'Diana', 'priority': 2 },
    ]
 
    print("Original order:")
    for item in items:
        print(f"  {item['name']}: priority {item['priority']}")
 
    print("\nUnstable sort by priority (may scramble ties):")
    unstable_result = quick_sort_unstable(items, key = lambda x: x['priority'])
    for item in unstable_result:
        print(f"  {item['name']}: priority {item['priority']}")
 
    print("\nStabilized sort by priority (preserves original order within ties):")
    stable_result = stable_sort_via_augmentation(
        items,
        key = lambda x: x['priority'],
        unstable_sort = quick_sort_unstable
    )
    for item in stable_result:
        print(f"  {item['name']}: priority {item['priority']}")

Method 2: Use a Stable Alternative

Often the simplest solution is to choose a different algorithm:

Instead of Quick Sort, use Merge Sort or Timsort
Instead of Heap Sort, use Merge Sort
Most language standard libraries offer stable sort options

Method 3: Tag-Based Stability (for specific algorithms)

For Quick Sort specifically, you can maintain stability by:

Using a three-way partition that collects equal elements in the middle
Not recursing on the middle (equal) partition
Maintaining original order within the equal partition

This is complex and typically not worth the effort—just use Merge Sort.

Practical Advice

If you need stability, use a stable algorithm directly. The index-augmentation technique is a last resort for when you're stuck with an unstable sort. Most standard libraries (Python, Java, modern JavaScript) already use stable sorts by default.

Language and Library Stability Guarantees

Different languages and libraries have different stability guarantees. Knowing these is essential for writing correct, portable code.

Sorting Stability by Language/Library
Language	Sort Function	Stable?	Algorithm Used
Python	sorted(), list.sort()	✅ Always	Timsort
Java	Arrays.sort(Object[])	✅ Always	Timsort
Java	Arrays.sort(primitives)	❌ Not guaranteed	Dual-Pivot Quicksort
JavaScript	Array.sort()	✅ Since ES2019	Implementation-dependent
C++	std::sort()	❌ No	Introsort usually
C++	std::stable_sort()	✅ Yes	Merge sort + insertion
C#	List.Sort()	❌ No	Introspective sort
C#	OrderBy (LINQ)	✅ Yes	Stable sort
Go	sort.Sort()	❌ No	Pattern-defeating quicksort
Go	sort.Stable()	✅ Yes	Stable sort variant
Rust	slice.sort()	❌ No	Pattern-defeating quicksort
Rust	slice.sort_stable()	✅ Yes	Merge sort

Java Primitive vs Object Sort

Java's Arrays.sort() uses DIFFERENT algorithms for primitives vs objects! Primitive sorts use Dual-Pivot Quicksort (unstable, but primitives have no identity so it doesn't matter). Object sorts use Timsort (stable). This is a common source of confusion.

stability_by_language.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Python: sorted() is ALWAYS stable (Timsort)
items = [
    {'key': 1, 'label': 'first'},
    {'key': 2, 'label': 'second'},
    {'key': 1, 'label': 'third'},  # Same key as first
]
 
# Stable sort guarantees: 'first' stays before 'third'
sorted_items = sorted(items, key=lambda x: x['key'])
for item in sorted_items:
    print(f"  key={item['key']}, label={item['label']}")
# Output:
#   key=1, label=first   <- comes before
#   key=1, label=third   <- comes after (preserves input order)
#   key=2, label=second

Advanced Multi-Level Sorting with Stability

Let's explore a sophisticated real-world example that showcases why stability is crucial for complex data organization.

Scenario: Organizing a Music Library

You have a collection of songs with multiple attributes. You want to organize them as:

By genre (alphabetically)
Within genre, by artist (alphabetically)
Within artist, by album release year (newest first)
Within album, by track number (ascending)

Approach 1: Sequential Stable Sorts (from least to most important)

music_library.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
from dataclasses import dataclass
from typing import List
 
@dataclass
class Song:
    title: str
    artist: str
    album: str
    year: int
    track: int
    genre: str
    
    def __repr__(self):
        return f"{self.track:2}. {self.title:20} | {self.artist:15} | {self.album:20} | {self.year}"
 
# Sample data
songs = [
    Song("Bohemian Rhapsody", "Queen", "A Night at the Opera", 1975, 11, "Rock"),
    Song("Born to Run", "Bruce Springsteen", "Born to Run", 1975, 1, "Rock"),
    Song("We Will Rock You", "Queen", "News of the World", 1977, 1, "Rock"),
    Song("Hotel California", "Eagles", "Hotel California", 1977, 1, "Rock"),
    Song("Thriller", "Michael Jackson", "Thriller", 1982, 4, "Pop"),
    Song("Billie Jean", "Michael Jackson", "Thriller", 1982, 6, "Pop"),
    Song("Beat It", "Michael Jackson", "Thriller", 1982, 5, "Pop"),
    Song("Bad", "Michael Jackson", "Bad", 1987, 1, "Pop"),
    Song("Smooth Criminal", "Michael Jackson", "Bad", 1987, 7, "Pop"),
]
 
print("Original order:")
for s in songs:
    print(f"  {s}")
 
# APPROACH 1: Sequential stable sorts (LEAST important key first)
# Sort order: genre → artist → year (desc) → track
 
# Step 1: Sort by track (least important)
by_track = sorted(songs, key=lambda s: s.track)
 
# Step 2: Sort by year DESCENDING
by_year = sorted(by_track, key=lambda s: s.year, reverse=True)
 
# Step 3: Sort by artist
by_artist = sorted(by_year, key=lambda s: s.artist)
 
# Step 4: Sort by genre (most important)
final = sorted(by_artist, key=lambda s: s.genre)
 
print("\nAfter sequential stable sorts (genre, artist, year desc, track):")
current_genre = None
current_artist = None
for s in final:
    if s.genre != current_genre:
        print(f"\n[{s.genre}]")
        current_genre = s.genre
        current_artist = None
    if s.artist != current_artist:
        print(f"  {s.artist}:")
        current_artist = s.artist
    print(f"    {s}")
 
# APPROACH 2: Single sort with composite key (more efficient)
print("\n" + "="*60)
print("APPROACH 2: Composite key (equivalent, more efficient)")
composite = sorted(songs, key=lambda s: (
    s.genre,     # Primary: ascending
    s.artist,    # Secondary: ascending
    -s.year,     # Tertiary: descending (negate for numbers)
    s.track      # Quaternary: ascending
))
 
current_genre = None
current_artist = None
for s in composite:
    if s.genre != current_genre:
        print(f"\n[{s.genre}]")
        current_genre = s.genre
        current_artist = None
    if s.artist != current_artist:
        print(f"  {s.artist}:")
        current_artist = s.artist
    print(f"    {s}")

Sequential vs Composite

Sequential stable sorts are conceptually clear and work with any stable sort. Composite keys are more efficient (single pass) but require all keys to be available and compatible (e.g., you can't negate strings for descending). Database engines often use sequential sorts for complex ORDER BY clauses.

Testing and Verifying Stability

How do you verify that a sorting implementation is stable? This is important for testing custom sort implementations or validating library behavior.

Test Strategy:

Create input with deliberately repeated keys
Tag each element with a unique identifier
Sort by the key
Verify that elements with equal keys maintain their original relative order

stability_test.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
import random
from typing import List, Tuple, Callable, TypeVar
 
T = TypeVar('T')
 
def test_sort_stability(
    sort_fn: Callable[[List[Tuple[int, int]]], List[Tuple[int, int]]],
    num_tests: int = 100,
    max_size: int = 100,
    key_range: int = 10
) -> Tuple[bool, str]:
    """
    Comprehensive stability test for a sorting function.
    
    Creates arrays with repeated keys and verifies stable behavior.
    Returns (is_stable, message) tuple.
    """
    for test_num in range(num_tests):
        # Generate test data: (key, unique_id) pairs
        # Many repeated keys to trigger potential instability
        size = random.randint(2, max_size)
        data = [(random.randint(0, key_range), i) for i in range(size)]
        
        # Sort by key only
        sorted_data = sort_fn(data)
        
        # Verify stability: for equal keys, unique_ids should be ascending
        for i in range(len(sorted_data) - 1):
            key_i, id_i = sorted_data[i]
            key_j, id_j = sorted_data[i + 1]
            
            # First check: sorted by key?
            if key_i > key_j:
                return False, f"Test {test_num}: Not sorted! {key_i} > {key_j}"
            
            # Stability check: equal keys should preserve original order
            if key_i == key_j and id_i > id_j:
                return False, (
                    f"Test {test_num}: Unstable! "
                    f"Elements with key={key_i}: id {id_i} came before id {id_j} "
                    f"but original order was reversed"
                )
    
    return True, f"All {num_tests} tests passed: Sort is stable"
 
# Test Python's built-in sort (should be stable)
def python_sort(arr):
    return sorted(arr, key=lambda x: x[0])
 
is_stable, message = test_sort_stability(python_sort)
print(f"Python sorted(): {message}")
 
# Test a simulated unstable sort
def unstable_sort(arr):
    # Adds random tiebreaker, destroying stability
    return sorted(arr, key=lambda x: (x[0], random.random()))
 
is_stable, message = test_sort_stability(unstable_sort)
print(f"Unstable sort: {message}")
 
# Custom handwritten sort test
def insertion_sort_stable(arr):
    """Stable insertion sort implementation."""
    result = []
    for item in arr:
        # Find insertion point: first position where key is greater
        pos = 0
        while pos < len(result) and result[pos][0] <= item[0]:
            pos += 1
        result.insert(pos, item)
    return result
 
is_stable, message = test_sort_stability(insertion_sort_stable)
print(f"Custom insertion sort: {message}")
 
def insertion_sort_unstable(arr):
    """Unstable insertion sort (uses < instead of <=)."""
    result = []
    for item in arr:
        pos = 0
        while pos < len(result) and result[pos][0] < item[0]:  # < not <=
            pos += 1
        result.insert(pos, item)
    return result
 
is_stable, message = test_sort_stability(insertion_sort_unstable)
print(f"Buggy insertion sort: {message}")

Summary: Mastering Stability

Key Takeaways

•Stability preserves relative order of equal elements — If a = b in input and a comes first, a still comes first in output.
•Stability enables multi-key sorting via sequential sorts — Sort by secondary key, then stable-sort by primary key.
•Stable algorithms include: Merge Sort, Insertion Sort, Counting Sort, Radix Sort, Timsort.
•Unstable algorithms include: Quick Sort, Heap Sort, Selection Sort.
•Unstable sorts can be made stable — Augment keys with original indices: (key, index).
•Language guarantees vary — Python is stable, Java primitives unstable, JavaScript stable since ES2019.
•Test stability with repeated keys — Generate data with ties, verify original order within ties preserved.
•Stability matters most when elements have identity beyond the sort key — Objects with multiple fields, records with meaning beyond the comparison key.

Module Complete: Sorting Formalization & Stability

You have now mastered the formal foundations of sorting: the precise mathematical definition, ascending vs descending order, comparison-based vs non-comparison paradigms, and the critical property of stability. These concepts form the conceptual bedrock upon which all sorting algorithms are built. In the next modules, you'll apply this understanding to specific algorithms, starting with the simple O(n²) sorts that illustrate fundamental techniques, then progressing to efficient O(n log n) algorithms and beyond.

What's Next:

With formal foundations established, the next module introduces Bubble Sort—not because it's practical, but because it perfectly illustrates the core operation of comparison-based sorting: comparing adjacent pairs and swapping when out of order. From this simple beginning, you'll develop intuition for how more sophisticated algorithms achieve their efficiency.