Binary search (04-01) left us with an outstanding bill: it demands a sorted list, and somebody has to sort it. We begin the study of sorting with the most natural algorithm of all: insertion sort, the one you run without realizing it when sorting cards in your hand or manually straightening out a scrambled arrivals board. It is not the fastest in general — it is O(n²) in the worst case — but it has virtues that keep it alive inside the most modern standard libraries: it is O(n) on nearly sorted data, it spends no extra memory, it is stable, and it works online. In this lesson we will implement it, trace it over the L1 arrivals, analyze it case by case with the method from 02-03, and learn a new concept that will accompany us throughout the module: stability.

1. The intuition: sorting cards, straightening boards
2. Commented in-place implementation
3. Full trace: six L1 arrivals
4. Case analysis: best O(n), worst and average O(n²)
5. Stability: what it is and why it matters
6. The superpower: nearly sorted data
7. Space and when to choose it

Imagine you receive cards one at a time and place them in your hand: you slide each new card to the left until it finds its spot among the ones you already have sorted. At no point is your hand out of order; it simply grows.

The RutaBus operator does the same thing when a stop's arrivals board gets scrambled: they walk down the list from top to bottom and, every time they find a time out of place, they pull it out and slide it up to where it belongs. That is exactly the structure of the algorithm:

• The list is conceptually divided into two zones: an already-sorted prefix (at the start, just the first element) and the unprocessed rest.
• At each step, the first unprocessed element (the "new card") is taken and inserted into its position within the prefix, shifting the larger ones to the right.
• When nothing remains unprocessed, the whole list is a sorted prefix.

The loop invariant — the reasoning technique from 04-01 — is: before processing element i, elements 0..i−1 are sorted with respect to each other.

Details worth understanding line by line:

• current = arrivals[i]: we keep a copy because the shifts are going to stomp on position i. This variable is all the extra space the algorithm uses.
• The while loop has two conditions and their order matters: j >= 0 must be evaluated before arrivals[j] > current, because if j reaches −1, arrivals[-1] in Python does not fail — it returns the last element (negative index!) — and would produce a silent error. The short-circuit evaluation of and protects us.
• arrivals[j] > current, strict: if they are equal, the loop stops and current is inserted after its equals. This apparently minor choice is what makes the algorithm stable (section 5).
• arrivals[j + 1] = current: on leaving the loop, j points at the last element ≤ current (or at −1 if there is none), so its spot is j + 1.

It is in-place: it rearranges within the list itself, without building a copy. It will cost O(1) of auxiliary space (02-02).

The Main Square board receives the upcoming L1 arrivals in the order the buses emitted them, not in time order:

(Times in "HH:MM" format compare fine as strings: alphabetical order matches chronological order when the format is fixed — the same trick we used with bisect in 02-03.)

We trace round by round of the for loop. The sorted prefix is shown in bold:

Total: 8 shifts and 12 comparisons for n = 6. Two observations from the trace:

• Round i = 3 (18:59) cost a single comparison: the element was already in place. The more elements arrive "in order", the more cheap rounds — this is the seed of the O(n) best case.
• Rounds i = 4 and i = 5 were expensive because the element came in "far out of place". The cost of each round is proportional to how far the element is from its final position.

The cost is dominated by the comparisons/shifts of the inner while. Let's apply the case analysis from 02-03 — this algorithm is the textbook example of why that analysis exists:

Best case — Θ(n): list already sorted. Every current is ≥ the whole prefix, the while does one comparison and zero shifts, and the for runs n−1 cheap rounds. Total ≈ n−1 comparisons. No comparison-based algorithm can go below that: at the very least you have to look at every element to certify it is sorted.

Worst case — Θ(n²): list in reverse order. Every current is smaller than the whole prefix and must travel all the way to the front: round i costs i shifts. Total:

Our old friend the arithmetic sum from 02-01 → Θ(n²). With the 6-arrival board reversed it would be 15 shifts; with RutaBus's 10,000 daily runs, ≈ 50 million.

Average case — Θ(n²): random order. On average, each element must cross half the prefix (the same uniform-distribution argument we used with find_stop in 02-03): round i costs ≈ i/2, and the total ≈ n(n−1)/4. Half the worst case in absolute value... and the same order Θ(n²) — "twice as fast in practice, the same order in theory", exactly as we learned it.

Couldn't we find the gap with binary search (04-01), since the prefix is sorted? Yes — it is called binary insertion and reduces the comparisons to O(n log n)... but the shifts are still n(n−1)/2 in the worst case, because the elements have to be moved regardless. It is the same lesson as insort in 02-03: binary search speeds up the finding, not the moving. The algorithm remains Θ(n²).

A sorting algorithm is stable if, when two elements tie on the sort key, they keep the relative order they came in with. It sounds like a pedantic detail until it bites you in production.

The North Station board shows arrivals from several lines, and two coincide in time:

We sort by time. The two 18:30 arrivals tie; a stable sort leaves them as they came (L2 before L1, perhaps because that was their emission order or because the list already came sorted by line); an unstable one may swap them arbitrarily.

Why does it matter? Because stability lets you sort by several keys by chaining sorts: if you first sort the board by line and then, with a stable algorithm, by time, you get "by time, and within the same time by line" — for free. With an unstable algorithm, the second sort destroys the work of the first.

Insertion sort is stable, and it is stable precisely because of the strict comparison arrivals[j] > current in the while: on a tie the loop stops and the new element lands to the right of its equals — that is, after them, as it arrived. If you wrote >=, the algorithm would still sort correctly... but it would stop being stable. One character of difference.

Let's sharpen the analysis. The real cost of the algorithm is proportional to the number of inversions in the input: pairs of elements that are in the wrong order with respect to each other. A sorted list has 0 inversions; a reversed one, n(n−1)/2; and each shift of the while fixes exactly one inversion. Therefore:

This explains its golden niche: nearly sorted data. The RutaBus arrivals board is fed by events that arrive almost in chronological order — only the occasional bus with a delayed emission inserts a time out of place. If every element is at most k positions from its spot, there are at most n·k inversions and the cost is O(n·k): with k small and constant, linear in practice. None of the "sophisticated" algorithms we will see later goes below O(n log n) in that scenario; insertion sort does it in O(n).

Hence it lives on inside modern libraries: production hybrid algorithms (we will see it with Timsort in 04-03) delegate the small or nearly sorted stretches to insertion sort.

Auxiliary space: O(1). Only current, i and j; all the movement happens inside the list itself. In the terminology of 02-02: total space O(n), auxiliary space O(1). It is the reference point against which we will measure merge sort's extra O(n) (04-03).

It is also online: it can keep sorting as elements arrive, without knowing the full sequence — exactly what record_arrival (02-03) did by keeping the board sorted insertion by insertion.

• Swapping the while conditions (arrivals[j] > current and j >= 0): with j = -1, Python evaluates arrivals[-1] — which raises no error but reads the last element — and the result is a badly sorted list without any exception to warn you. The short circuit of and only protects you if j >= 0 comes first.
• Forgetting the current copy: if you work directly with arrivals[i], the first shift overwrites it and you duplicate one element while losing another. Typical symptom: the list ends up "sorted" but with repeated values that were not there.
• Inserting at j instead of j + 1: on leaving the loop, j points at the last element less than or equal — the gap is the next position. Quick mental test: if current is the largest of all, the loop runs zero times and j + 1 == i, which means leaving it where it was. Correct.
• Breaking stability with >=: it sorts just as well, so no "is it sorted?" test detects it; you will only notice when the secondary order of ties matters. If your test does not include duplicate keys, you are not testing stability.
• Tip: to verify a sorting implementation, compare it against sorted() with random lists, including empty, single-element, with duplicates, and in reverse order. Five lines of test loop catch 99% of the bugs.

Trace (a table like the one in section 3) insertion_sort over the board ["18:05", "18:12", "18:31", "18:59", "18:01"]. Before tracing, predict: will it be a cheap run or an expensive one? Which element takes almost all the cost? Count total comparisons and shifts.

The board stores (time, line) tuples and must be sorted by time only while preserving stability. Adapt insertion_sort so that it compares only by the first field of the tuple, and demonstrate with board = [("18:30", "L2"), ("18:05", "L1"), ("18:30", "L1")] that the two 18:30 ties keep their relative order.

Every night RutaBus receives the day's arrivals file "nearly sorted": at most, each record is displaced k = 3 positions from its place. The team is debating between insertion sort and an O(n log n) algorithm. With n = 100,000: (a) estimate insertion sort's operations using the O(n·k) bound; (b) compare it with n·log₂ n; (c) what would you recommend, and which question from 02-03 ("which case matters?") lies behind the decision?

Solution 1

Prediction: the first four elements already come sorted, so their rounds will be cheap; "18:01" is the minimum and arrives last — it will have to cross the entire prefix. A near-best-case run with one worst-case round.

Comparisons: 1 + 1 + 1 + 4 = 7. Shifts: 4, all from the last round. A single element out of place (with 4 inversions) turns an O(n) run into O(n) + 4 — still cheap, consistent with the "n + inversions" bound.

Solution 2

The two 18:30 arrivals keep L2 before L1, as in the input: stable. If you change > to >= you get [('18:05','L1'), ('18:30','L1'), ('18:30','L2')] — still sorted by time, but with the tie inverted.

Solution 3

(a) Insertion sort bound: n·k = 100,000 × 3 = 300,000 shifts at most (plus the ~n cheap comparisons: same order). (b) n·log₂ n ≈ 100,000 × 17 ≈ 1,700,000 operations. Insertion sort does ~5–6 times less work, with simpler code and O(1) memory. (c) Recommendation: insertion sort, as long as the premise "k ≤ 3" is guaranteed. The underlying question is the one from 02-03: is the favorable case the frequent one and is it guaranteed? If one day the file arrives in arbitrary order (an upstream failure), insertion sort shoots up to Θ(n²) ≈ 5·10⁹ operations. Engineering decision: either validate the premise (measure the disorder before choosing), or use a hybrid that degrades gracefully — exactly what Timsort does, as we will see in the next lesson.

Insertion sort maintains a sorted prefix and inserts each new element into its place by shifting the larger ones: stable (thanks to a strict comparison), in-place with O(1) auxiliary, online, Θ(n) on already sorted data and Θ(n²) on average and in the worst case — with a real cost of "n + inversions" that makes it the king of the small and the nearly sorted, like the RutaBus arrivals boards. But its Achilles' heel is plain to see: over the 10,000 daily runs in arbitrary order, the ~25 million operations of the average case are not acceptable. To break the O(n²) barrier we need to stop moving elements one at a time and attack the problem with the strategy from 03-01: divide the list, sort the halves, and combine them. That is merge sort — and with it, at last, we will solve the recurrence T(n) = 2·T(n/2) + O(n) we left pending in Module 3.