Data Structures & Algorithms / Ordered structures and graph reasoning / Lesson 7

Sorting, stability, and merge invariants

Preserve a sorted permutation, define equal-key behavior, and account for preparation and copying costs.

About 5 min readContent reviewed 2026-10-28

On this page

Lesson goals

Sorted output must also preserve the input multiset
Merge two sorted prefixes by their next candidate
Derive time and peak storage from the implementation

Sorted output must also preserve the input multiset

Sorting requires two properties: keys appear in the requested order, and every input occurrence appears exactly once in the output. A function that returns an empty list is ordered but not a valid sort of nonempty input. Specify whether sorting mutates the original sequence and whether equal-key records retain their original relative order. That last property is stability. It matters when records were already ordered by another criterion or when arrival order resolves ties. Stable does not mean that different inputs always produce the same order; it preserves the order supplied among equal keys.

Merge two sorted prefixes by their next candidate

During a merge, the output is the correctly ordered prefix of all processed occurrences, while each input cursor points to its first unprocessed occurrence. The smallest remaining key must be at one of those cursors because both inputs are already sorted. Taking from the left on equality preserves cross-half arrival order. The first program applies this rule recursively after dividing the input. Its base case returns a copy of zero or one element. This implementation uses slices for clarity, so the analysis includes their copying and does not call the sort in-place.

python Self-contained Python3 algorithm example using synthetic local data.

def merge_sort(items, key=lambda item: item):
    if len(items) < 2:
        return list(items)
    middle = len(items) // 2
    left = merge_sort(items[:middle], key)
    right = merge_sort(items[middle:], key)
    i = j = 0
    output = []
    while i < len(left) and j < len(right):
        if key(left[i]) <= key(right[j]):
            output.append(left[i])
            i += 1
        else:
            output.append(right[j])
            j += 1
    output.extend(left[i:])
    output.extend(right[j:])
    return output

records = [(2, "A"), (1, "B"), (2, "C"), (1, "D")]
print(merge_sort(records, key=lambda record: record[0]))
print(records)

Expected output

[(1, 'B'), (1, 'D'), (2, 'A'), (2, 'C')]
[(2, 'A'), (1, 'B'), (2, 'C'), (1, 'D')]

The original list remains unchanged, and B precedes D while A precedes C within equal keys.

Derive time and peak storage from the implementation

Each merge level processes a total of O(n) elements, and balanced splitting gives O(log n) levels, yielding O(n log n) work under bounded-cost comparisons and key evaluation. Peak auxiliary storage is O(n) for the lists plus O(log n) call frames; cumulative allocation over the run can be larger than peak live memory. The custom example recomputes keys during comparisons. An expensive key changes its practical cost, unlike Python’s built-in key sorting, which evaluates a key once per input record. Distinguish those implementations rather than transferring a library guarantee to arbitrary teaching code.

Use standard sorting for application work

The second program sorts by a compound key: score first, then name. A compound key makes the complete ordering visible, while stability still preserves input order if both fields tie. Python sorted creates a new list; list.sort mutates and returns None. Do not assign the return of list.sort as the sorted data. For multiple stable passes, sort the less significant field first and the more significant field last. Choose the explicit contract that reviewers can understand, and keep locale-aware collation separate from ordinary code-point string comparison when user-facing language order matters.

python Self-contained Python3 algorithm example using synthetic local data.

records = [
    {"name": "Rivers", "score": 2},
    {"name": "Maps", "score": 1},
    {"name": "Atlas", "score": 2},
]
ordered = sorted(records, key=lambda record: (record["score"], record["name"]))
print([record["name"] for record in ordered])
print([record["name"] for record in records])

Expected output

['Maps', 'Atlas', 'Rivers']
['Rivers', 'Maps', 'Atlas']

The compound key resolves score ties alphabetically under ordinary Python string ordering; no locale collation is claimed.

Ordering must be coherent before algorithms rely on it

A comparator or key policy must define behavior for every accepted input. Mixed incomparable types, inconsistent custom comparisons, and floating NaN values can violate assumptions behind a simple sorted-order argument. Normalize or reject unsupported values at the boundary according to the domain. Do not hide errors by turning every key into a string, since numerical 10 and 2 then have a different order. Stable sorting cannot repair an invalid ordering relation. Also include output size in the result contract: materializing a sorted list requires storage even when the input is an iterator.

Test permutation, order, stability, and ownership

Compare the custom sort with sorted on tiny arrays containing negatives and duplicates. Check multiplicity as well as monotonic order, and use labeled equal-key records to expose unstable tie handling. Verify the original list remains unchanged under this function’s contract. Empty and singleton inputs exercise the base case, while reverse-sorted data exercises merges throughout the tree. A finite differential suite does not replace the merge invariant and shrinking-subproblem proof. Keep correctness tests separate from performance measurements; a handful of small examples cannot establish comparative runtime superiority.

Common errors and fixes

Equal-key records swap relative order

Why it happens: The merge chooses the right half on equality.
How to fix it: Choose the left occurrence when equal keys must preserve arrival order.
Prevent it next time: Test distinct labels sharing the same key.

The sorted variable becomes None

Why it happens: The return value of list.sort was treated as a new list.
How to fix it: Use sorted or mutate the existing list without assigning the return.
Prevent it next time: Document mutation and return contracts together.

A key changes numerical meaning

Why it happens: Values were stringified merely to avoid comparison errors.
How to fix it: Validate accepted types and choose a domain-correct key.
Prevent it next time: Include 2 and10 in ordering fixtures.

Check your understanding

1. Why does replacing <= with < threaten merge stability?

Show worked solution

When keys are equal, the condition becomes false and the right-half item is emitted before an earlier left-half occurrence. Both outputs remain numerically sorted, so value-only tests miss the defect. Labeled equal-key records and their original positions expose it.

2. Can a sort be ordered but lose correctness?