How Insertion Sort Works

Most sort files in this repository use list as the collection type with no constraint, accepting any input and relying on Python's dynamic dispatch to raise at runtime if the elements are not comparable. This file takes a different approach. The Comparable Protocol on lines 20 and 21 declares that the only requirement is a __lt__ method (less-than). The TypeVar on line 24 is bound to that Protocol, which means mypy can verify at type-check time that any type passed to insertion_sort supports <. The positional-only slash in the __lt__ signature (/) is a Python 3.8+ convention for parameters that must be passed by position; Protocols use it to avoid requiring the parameter name to match. This is the canonical contribution checklist pattern for a generic sort function.

The PEP 695 type-parameter syntax on line 27 (def insertion_sort[T: Comparable]) is Python 3.12+ shorthand for the TypeVar declared above. Both forms are valid at the pinned SHA's minimum Python 3.14; the TypeVar is kept in the file for clarity. The six doctests expand the contract beyond integers. The empty-list test on line 37 verifies the function returns an empty list rather than raising a division-by-zero or index error. The string test on line 41 verifies that the Comparable bound works at runtime for types other than int. The two 100-element random sample tests at the end serve as a statistical check: if the sort were wrong for some input shapes, a random sample would eventually catch it.

Line 54 saves the current element into insert_value before the while loop overwrites it. That saved copy is the key to the shift approach. The while loop on lines 55 and 56 does not swap; it copies the left neighbor into the current slot and decrements the index. Each step shifts one element one position to the right, opening a gap for insert_value. When the while condition fails (either the index reaches zero or the left neighbor is already smaller), line 58 drops insert_value into the gap. A swap-based sort would write three times per step (temp = a; a = b; b = temp); this shift approach writes once per step. That matters when writes are expensive. The loop invariant is that collection[:insert_index] is sorted at the start of every outer-loop iteration, and the inner loop preserves it.

This __main__ block imports testmod with a targeted from doctest import testmod rather than the module-level import doctest you see in merge_sort.py. Both patterns are equivalent at runtime; the from-import style is marginally cleaner because it avoids the doctest. prefix on line 65. After the doctests run, the driver reads a comma-separated string, strips trailing whitespace, splits on commas, converts each token to an integer, and prints the sorted result using the debug f-string format (= suffix). Unlike the bubble sort file, there is no guard against an empty input: pressing Enter without typing anything raises ValueError from int(item) on the empty string. That difference is a contributor style choice, not a policy requirement.

The O(n squared) label is accurate for large input but misleading for small input. On a list of ten elements the outer loop runs nine times and the inner loop runs at most nine times per outer iteration, for at most 81 comparisons. Quicksort on ten elements pays the cost of a pivot selection, two recursive calls, and the function-call overhead for each sub-list. Mergesort allocates new sublists on every recursive level. Insertion sort avoids both: no allocation, no recursion, and a sequential memory-access pattern that fits in L1 cache. CPython's built-in sorted() uses Timsort, which identifies nearly-sorted runs in the input and uses a galloping merge; for runs shorter than 64 elements it falls back to insertion sort. Reading this loop is reading the inner engine of Python's own sort. See the Sorting Algorithms category tour for the full picture across sorts/.