211: Elementary Sorting: Selection, Bubble, Insertion, Stability, and Invariants

Learning outcomes

By the end of this lesson, you can:

explain and apply selection sort in a realistic implementation;
explain and apply bubble sort in a realistic implementation;
explain and apply insertion sort in a realistic implementation;
explain and apply stability in a realistic implementation;
explain and apply comparison model in a realistic implementation.

These outcomes are connected rather than independent vocabulary items. The three algorithms give you different ways to maintain order; stability describes an important behavioral guarantee; and the comparison model explains why these straightforward algorithms are not usually the right answer for large inputs. In each case, the useful question is what the implementation guarantees, what it costs, and which input assumptions make that cost acceptable.

Prerequisites and retrieval

This lesson assumes the earlier 01–06 foundation and the preceding lessons in this module. Before reading, retrieve one concrete example from a previous project where the same concern appeared. Perhaps you sorted records for a table, processed a list that was already nearly ordered, or relied on a library sort without checking what happened to equal keys. The point is not to memorize a template. It is to make a defensible decision in an interview-sized problem and in a production data-processing problem, where the right choice follows from constraints rather than habit.

Terminology

Selection sort: Repeatedly select the minimum remaining element and place it at the boundary between the sorted and unsorted portions.
Bubble sort: Compare neighboring elements and swap them when they are out of order, allowing large elements to move toward the end of the unsorted portion.
Insertion sort: Maintain a sorted prefix and insert each next element into the position where it belongs within that prefix.
Stability: A stable sort preserves the original relative order of records whose keys compare as equal.
Comparison model: General comparison sorting has an Ω(n log n) lower bound in the comparison decision-tree model. A sort that runs in O(n) therefore needs extra assumptions about the keys, such as a bounded integer range.
Sorting contracts: Define comparator consistency, mutation policy, and handling of NaN, locale, and case in production code. The algorithm cannot compensate for an ambiguous ordering contract.

Mental model

Treat Elementary Sorting: Selection, Bubble, Insertion, Stability, and Invariants as a design problem with observable inputs, outputs, invariants, and failure modes. Simple O(n²) sorts are useful because their state is small enough to inspect after every iteration. They let you practice proving a sorted region, reasoning about stability, recognizing adaptive behavior, and distinguishing in-place mutation from allocation. Production libraries usually use more advanced hybrids, but the underlying reasoning does not become less relevant when the implementation gets faster.

For these algorithms, picture an array divided into a sorted region and an unsorted region. The boundary moves as the algorithm progresses. The invariant is the statement that remains true at that boundary: selection sort has placed the smallest remaining value at each completed position; bubble sort has pushed the largest remaining value to the end after each pass; insertion sort has kept its prefix sorted after each insertion. A strong implementation makes the comparator and mutation policy explicit, narrows uncertainty at the boundaries, and leaves enough evidence through tests, types, constraints, metrics, or diagrams to show why the design is safe.

A useful interview and production sequence is:

requirement -> constraints -> model -> implementation -> failure analysis -> verification

Do not jump from a requirement directly to a library call. First state what must remain true. Then choose the mechanism that enforces it. This is where people usually get confused: the name of an algorithm is not a correctness argument. The loop invariant, comparator, and handling of equal values are what determine whether the result satisfies the contract.

Deep dive

1. Selection sort

Selection sort repeatedly scans the unsorted suffix, finds its minimum, and swaps that value into the next boundary position. After iteration i, the prefix before i is sorted and contains the same elements as the original prefix of the final result. That is the central loop invariant. The next scan can therefore ignore the completed prefix.

It performs O(n²) comparisons regardless of whether the input is random, reverse-sorted, or already sorted. In the usual swap-based implementation it performs at most O(n) swaps and uses O(1) additional storage, which can matter when writes are more expensive than comparisons. It is typically not stable: swapping the selected minimum across equal keys can change their original order. Its simplicity makes the invariant easy to prove, but its quadratic scan makes it a poor choice for large arrays.

Decision rule: Use selection sort deliberately when its small number of writes or its straightforward invariant makes the contract easier to prove. If it only reduces typing while hiding the input-size assumption, prefer a more explicit design or a library implementation with documented behavior.

2. Bubble sort

Bubble sort compares adjacent elements and swaps them when the left element belongs after the right one. During a pass, larger values move toward the end, one adjacent swap at a time. After a complete pass over the active range, the final position in that range is correct. The active range can shrink because that position no longer needs attention.

With an early-stop flag, bubble sort detects an already sorted input: if a full pass makes no swaps, the algorithm can terminate. That gives it a best-case time of O(n) for an already sorted array, while its average and worst-case time remain O(n²). It uses O(1) additional storage. If it swaps only when the left key is strictly greater than the right key, it can be stable because equal records are not reordered. The stability property depends on that implementation detail and on the comparator, not merely on the algorithm's name.

Decision rule: Use bubble sort deliberately when the pass invariant or early-stop behavior is useful for a small, educational, or already-nearly-sorted input. If the implementation only reduces typing while hiding the quadratic worst case, prefer a more explicit design.

3. Insertion sort

Insertion sort treats the first element as a sorted prefix, then takes each following element and shifts larger prefix elements one position to the right until the next element can be inserted. Before processing position i, the prefix [0, i) is sorted. After the shifts and insertion, [0, i + 1) is sorted and contains exactly the same values as before. That is the loop invariant to state before writing the loops.

Insertion sort is stable when it shifts only elements strictly greater than the value being inserted. Equal elements remain in their original order. It is in-place, using O(1) additional storage, and its best-case time is O(n) when the input is already sorted. Its average and worst-case time are O(n²), with reverse-sorted input producing the maximum number of shifts. Because it has low overhead and performs well on small or nearly sorted ranges, hybrid algorithms often use it for tiny partitions.

Decision rule: Use insertion sort deliberately when the input is small or likely to be nearly sorted and its prefix invariant and stable behavior fit the contract. If the input may be large and disordered, do not let its pleasant small-example behavior conceal the quadratic worst case.

4. Stability

Suppose records have a score key and an id that records their original order. Sorting by score should not silently change the order of records with the same score if a later operation depends on that prior ordering. A stable sort preserves that relative order; an unstable sort may not.

Stability matters when sorting in stages. For example, if records are first sorted by name and then stably sorted by department, names remain ordered within each department. It also matters when equal-key records carry meaningful arrival order, priority, or another previously established ranking. A comparator that treats two records as equal must be paired with an algorithm and implementation that preserve the contract if stability is required.

There is a practical cost: a stable implementation may need extra memory or additional movement, depending on the algorithm. Do not assume that “equal” means the records are interchangeable. State whether the sort mutates the input, whether it is stable, and what comparator semantics apply to special values such as NaN, strings with locale rules, or differing case.

Decision rule: Use stability deliberately when it makes the contract or invariant easier to prove. If stability is not required, do not pay for it accidentally; if it is required, do not assume it from a method name without checking the language or library contract.

5. Comparison model

All comparison-based sorting algorithms learn about the input through questions such as “does a come before b?” In the comparison decision-tree model, distinguishing all possible orderings requires Ω(n log n) comparisons in the general case. That lower bound explains why a general-purpose comparison sort cannot guarantee O(n) time for arbitrary values.

Linear-time approaches are possible only when they use additional information about the keys. Counting sort can exploit a small bounded integer range; radix sort can process digits or characters under suitable representation assumptions; bucket-based methods depend on distribution assumptions. These are not contradictions of the lower bound because they do more than compare arbitrary elements. Their extra assumptions introduce their own memory, range, distribution, and key-normalization trade-offs.

Decision rule: Use the comparison model deliberately when it makes the contract or invariant easier to prove. If an O(n) claim appears, identify the key assumptions that support it instead of accepting the complexity label in isolation. If those assumptions do not hold, a comparison sort with O(n log n) behavior is the more honest choice.

6. Sorting contracts

Define comparator consistency, mutation policy, and handling of NaN, locale, and case in production code. A comparator should describe a consistent ordering: if it reports contradictory results, the algorithm may produce output that is not meaningfully sorted, and a library sort may behave unpredictably. The comparator also needs a clear answer for values that look equal under the chosen key.

Decide whether sorting mutates the input array or returns a new array. Mutation can reduce allocation but can surprise callers that share the reference. A non-mutating approach can make ownership clearer but consumes additional storage. For strings, specify whether ordering is code-unit, case-insensitive, or locale-aware. For numbers, decide how NaN is handled rather than allowing it to fall through an ordering that was designed only for ordinary numeric values.

Decision rule: Use sorting contracts deliberately when they make the behavior and invariant easier to prove. If the library call hides the comparator, mutation, or special-value assumptions, prefer the design that makes those decisions inspectable. A mathematically invalid comparator is not a minor formatting issue; it invalidates the result's meaning.

Worked example

Consider an interview-sized problem and a production data-processing problem, so the learner must reason from constraints rather than memorize a template. Start by writing the requirement in one sentence, list the input and output contracts, and identify which of the concepts above owns each failure mode. For a sorting task, include the ordering key, whether equal keys must remain stable, whether the input may be mutated, and the credible input size. The important move is separation: parsing or validation belongs at the boundary; domain rules belong in the domain or service layer; persistence rules belong in the database or repository; presentation rules belong in the client. Mixing these concerns makes a happy-path demo look shorter but makes edge cases much harder to reason about.

The example below is intentionally small and focuses on the invariant pattern rather than implementing one of the sorting algorithms. The variable answer is the best value seen so far; after each iteration, it represents the maximum of the processed prefix. That same habit of stating what is true after each step is what lets you reason about a sorting boundary.

function solve(values: readonly number[]): number {
  let answer = 0;
  // State the invariant before choosing the data structure.
  for (const value of values) {
    answer = Math.max(answer, value);
  }
  return answer;
}

There is an edge case hidden in this code: returning 0 is correct only if the input contract says values are non-negative and an empty input has answer 0. If negative values are valid, the initialization changes; if an empty array is invalid, the function should reject it rather than quietly return a value. The code is therefore a useful reminder that an invariant depends on the contract surrounding it, not only on the loop body.

Walk the example with at least four cases: the normal path, an empty or missing value, a duplicate/retry/concurrent path where relevant, and a dependency failure. For sorting, make the cases concrete: already sorted input, reverse-sorted input, duplicate keys whose original order must be inspected, and a missing or malformed record. For each case, state which layer detects the problem and what the caller observes. This is the level of explanation expected in a senior code review or technical interview.

Production perspective

Production correctness is broader than “the code works on my machine.” Ask how the design behaves during deploys, retries, partial failure, stale clients, concurrent requests, malformed data, schema changes, and high cardinality. Sorting also has operational boundaries: an unexpectedly large input can turn an O(n²) implementation into a latency or resource problem, and sorting a shared array in place can create a surprising change for another consumer.

Prefer explicit contracts, bounded resource usage, structured errors, and measurable behavior. Optimize only after you can identify the bottleneck or risk with evidence. Measure representative input sizes and distributions, not only a tiny random sample. Check whether the cost is comparisons, swaps, memory allocation, serialization, or downstream work; “faster sort” is not a useful conclusion without knowing which cost matters.

When the topic involves an external dependency, define a timeout and cancellation strategy. When it involves persistence, define transaction and consistency expectations. When it involves user-visible state, define loading, empty, error, stale, and success states. When it involves security, assume the client can be modified and the network input is untrusted. A sorting function may look local, but the records it receives can still be malformed or attacker-controlled, and its output may influence authorization, pricing, pagination, or display behavior.

Guided lab

Implement insertion and selection sort, annotate the loop invariant, and test stability with records containing equal keys. Compare operations on sorted, reverse-sorted, and random inputs. Record comparisons, swaps, and shifts separately so that you can distinguish the algorithms' behavior instead of relying only on elapsed time. Confirm whether each implementation mutates its input and document the comparator contract.

For the stability test, give equal-key records distinct IDs and assert the IDs remain in their original order after sorting. Test the same fixture with a deliberately unstable swap pattern so you can see why the guarantee is about records, not just the sequence of keys. Include an empty array, a one-element array, duplicate values, all-equal values, negative values if the comparator allows them, and the smallest and largest credible input sizes.

Complete the lab with this discipline:

Write the requirement and two non-requirements.
List input, output, and error contracts before implementation.
Implement the smallest correct vertical slice.
Add at least one invalid-input test and one edge-case test.
Instrument or inspect the behavior instead of guessing.
Refactor one hidden assumption into an explicit type, constraint, function, or configuration.
Explain one alternative design and why you did not choose it.
Record a short “what would break at 10× scale?” note.

For the complexity note, include best, average, and worst-case time where they differ, plus additional space and stability. Explain why the observed counts match the invariant. A good lab result does not merely report that the array is sorted; it gives evidence that the implementation preserves the intended contract for equal keys, boundary positions, and input ownership.

Edge cases and failure modes

Selection sort: Test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Include already sorted and reverse-sorted arrays, all-equal values, and a comparator that distinguishes records from their keys.
Bubble sort: Test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Verify the early-stop flag, including a case where one late swap is still required, and confirm that equal records are not swapped when stability is promised.
Insertion sort: Test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Include empty and one-element prefixes, reverse order, all-equal records, and values inserted at the beginning, middle, and end.
Stability: Test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Use equal keys with observable IDs and verify their original relative order after one sort and after a staged sort.
Comparison model: Test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Check that any claimed O(n) alternative actually states its range, representation, or distribution assumptions and handles keys outside them.

Also test the sorting contract itself. A comparator that returns inconsistent results, mishandles NaN, or applies an undocumented locale or case rule can make a correct algorithm appear broken. A function that mutates a caller-owned array can pass output assertions while still violating the API contract.

Common mistakes and debugging

Solving the example instead of the requirement: a copied pattern can be syntactically correct but architecturally wrong. State the key, stability requirement, mutation policy, and input-size constraint first.
Hiding uncertainty with assertions, broad exception handlers, permissive schemas, or “temporary” any values. These approaches can conceal malformed records or an invalid comparator instead of defining how they should be handled.
Testing only the happy path and therefore discovering contracts only after integration. Test duplicates, empty input, reverse order, special numeric values, ownership, and the largest credible size before depending on the implementation.
Optimizing before measuring, or selecting a scalable mechanism without a scale requirement. Count comparisons and writes, establish a baseline, and choose a faster mechanism only when the workload justifies its added assumptions or complexity.
Letting client-side behavior stand in for server-side authorization, validation, or persistence guarantees. The client can be modified, bypassed, or out of date; sorting input in a UI does not validate the data at the system boundary.

For debugging, reproduce the smallest failing case, inspect the actual value or execution plan, trace the boundary where the invariant first becomes false, and fix the owning layer rather than adding a downstream patch. In a sorting loop, inspect the sorted and unsorted regions after each iteration, the comparator result for the failing pair, and whether an equal-key swap changed record order. Check the input before and after the call when mutation is in question. If the output is not ordered, find the first adjacent pair that violates the comparator; that usually narrows the defect faster than printing the entire array.

Interview questions

What problem does Selection sort solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Bubble sort solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Insertion sort solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Stability solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Comparison model solve, and what trade-off or failure mode would make you choose a different approach?

When answering, do more than name O(n²). State the invariant, best and worst cases where relevant, additional space, stability behavior, and the input contract that makes the choice reasonable. Be ready to explain why a library sort is acceptable only after its comparator and mutation or stability guarantees match the requirement.

Checkpoint

Without notes, explain Elementary Sorting: Selection, Bubble, Insertion, Stability, and Invariants to another developer in five minutes. Your explanation must include one invariant, one edge case, one production failure mode, and one alternative design. Then implement a small example without copying the lesson code.

Your explanation should connect the choices rather than list vocabulary. For example, describe how the sorted boundary advances in selection sort, how an early-stop pass changes bubble sort's best case, how insertion sort maintains a prefix, and how equal-key records expose stability. Then connect those observations to the comparison-model lower bound and to a production sorting contract. If you cannot say what the comparator assumes or what evidence would prove the choice works, the design still has an unresolved assumption.

Mastery checklist

I can define the core terms precisely.
I can choose a design from requirements instead of from habit.
I can implement and test the normal path and edge cases.
I can explain the runtime, storage, or complexity cost.
I can identify which layer owns validation, errors, and recovery.
I can compare at least two reasonable alternatives.
I can explain how the design changes at larger scale or stricter reliability.