Getting Started: Insertion Sort, Merge Sort & Loop Invariants

By the end you will be able to trace and implement insertionSort and mergeSort by hand, prove an algorithm correct using a loop invariant (the Initialization / Maintenance / Termination method), analyse running time with a line-by-line cost model (c_i·t_j, best/worst/average case), and recognise the divide-and-conquer pattern that reappears throughout this track.

1. The sorting problem & insertionSort

Picture sorting a hand of playing cards. You hold the first card (already "sorted" — one card is trivially in order). You pick up the next card and slide it left, past every card bigger than it, until you find its spot, then drop it in. You repeat this — pick the next card, slide it into place among the cards you've already arranged — until every card in your hand is in order. That is exactly insertion sort.

The sorting problem: given a list of n numbers, produce a reordering (a permutation) of those same numbers in which every value is ≤ the one after it. The array a you are handed is one instance of the problem; insertionSort is one particular algorithm — a well-defined, finite sequence of steps — that solves every instance.

This track's pseudocode is 0-indexed, exactly like Dart (the first element is a[0]); indentation shows nesting instead of braces, ← means "store into", and a loop variable keeps its final value after the loop ends. Here is insertionSort(a), where n = a.length:

insertionSort(a)

In words: for every position j from index 1 onward, pull that element out as key, then slide every larger element in the already-sorted prefix a[0..j−1] one slot to the right, and drop key into the gap that opens up.

A beginner trap: it looks like insertion sort "swaps" adjacent elements one at a time, like bubble sort. It doesn't — line 5 shifts a[i] one slot right (a single assignment, no temporary swap variable needed), and only once the correct gap is found does line 7 drop key in. Watch the animation closely: key is held outside the array the whole time it's being positioned.

Now the case that makes insertion sort do the most work — a reverse-sorted array, where every new key must slide all the way to the front:

Try your own array (comma-separated whole numbers, up to 8 values so the animation stays readable):

Dart implementation — the pseudocode translates line for line, because both are 0-indexed (the outer loop runs j = 1 .. n-1; a[0] alone is already a sorted prefix).

Notice the test i >= 0: index 0 is a legal slot, so the scan must be allowed to reach it. Writing i > 0 instead (a habit carried over from pseudocode that counts from 1) is a classic bug — see the debugging question in the interview bank below.

Input size → what is feasible: Θ(n²) worst/average case: n = 5·10³ → at most n(n−1)/2 = 1.25·10⁷ shifts (instant); n = 10⁵ → 5·10⁹ shifts (~50 s) is too slow → use mergeSort (Θ(n lg n)) or the library sort. On nearly-sorted input (D inversions) the cost is only Θ(n + D), so n = 10⁶ with D ≤ 10⁶ is still fine.

insertionSort grows a sorted prefix one element at a time by inserting each new element into its correct place among the elements already placed. It sorts in place (only a constant amount of extra space) and is stable (equal elements keep their relative order, since the while-loop only shifts strictly-greater elements).

2. Loop invariants: proving insertionSort correct

A loop invariant is like a claim you re-check at the start of every lap of a race: "at the start of lap k, I have already covered exactly (k−1) laps' worth of distance, correctly." If that claim is true before lap 1 (initialization), and being true before any lap guarantees it's still true before the next lap (maintenance), then when the race ends (termination) the claim tells you something useful and guaranteed about the finish.

We prove algorithms correct with exactly three steps, applied to a claim about the state of the array just before each iteration of the outer loop:

Initialization — the invariant is true before the first iteration.
Maintenance — if it's true before an iteration, it's still true before the next one.
Termination — when the loop ends, the invariant (plus the reason the loop ended) proves the algorithm correct.

insertionSort's loop invariant (for the outer for j from 1 to a.length − 1 loop): at the start of every iteration of the for loop, the subarray a[0..j−1] consists of the elements originally in a[0..j−1], but in sorted order.

Initialization: before the first iteration, j = 1, so the claim is about a[0..0] — a single element, trivially "sorted".
Maintenance: the body of the for loop (lines 2–7) takes a[j] and inserts it into its correct place among the already-sorted a[0..j−1], producing a sorted a[0..j] — the invariant holds for the next value of j. (Watch this happen in the animation above: every time a frame shows "invariant restored", a[0..j] is sorted.)
Termination: the loop ends when j reaches n (one past the last index n − 1). Plugging j = n into the invariant: a[0..n−1] is sorted — which is exactly what insertionSort is supposed to produce. The invariant at termination IS the correctness proof.

The same three steps as running code — the invariant is checked at the start of every outer iteration (Initialization at j = 1, Maintenance at every later j) and once more when the loop ends (Termination):

A loop invariant must be true (1) before the loop starts, (2) preserved by every iteration, and (3) meaningful when the loop stops. This exact three-part method (Initialization / Maintenance / Termination) reappears for every non-trivial algorithm later in this track — merge, quicksort's partition, graph algorithms, all of them.

3. Analyzing algorithms: the RAM model & cost table

The RAM (Random-Access Machine) model pretends the computer is an idealized single worker who does one basic step at a time — one comparison, one assignment, one arithmetic operation — each taking exactly one "tick", with instant access to any memory address (no caches, no slow disk, nothing realistic about hardware — just enough abstraction to count steps fairly across different algorithms).

To analyze running time, assign a constant cost c_i to each line i of pseudocode (the actual value of c_i depends on the machine, but it doesn't matter for the shape of the answer), and count how many times each line executes. For insertionSort, let t_j be the number of times the while test on line 4 is checked for that particular value of j. This gives the exact running time (sums run over j = 1 … n−1):

T(n) = c₁n + c₂(n−1) + c₃(n−1) + c₄·Σt_j + c₅·Σ(t_j−1) + c₆·Σ(t_j−1) + c₇(n−1)

The value of t_j is what makes the running time depend on the input, not just its size:

Best case — already sorted: the while-loop body never runs; every t_j = 1. Every term becomes a constant times n (or n−1), so T(n) = an + b — linear.
Worst case — reverse sorted: every new key must slide past every element already placed, so t_j = j + 1 (j shifts plus the one failing test). Then Σt_j = Σ_j=1..n−1 (j + 1) = n(n+1)/2 − 1, which has an n² term, giving T(n) = an² + bn + c — quadratic.
Average case: on a random ordering, a key is expected to be past about half of the already-sorted elements, so t_j ≈ j/2 — still Θ(n²), just with smaller constants than the worst case.

Here is that formula applied to the exact two arrays animated above, with each t_j counted by really running the algorithm:

The same cost model as code: lineCounts runs insertionSort and counts how many times each numbered line executes, runningTime is the T(n) formula above, and the closed forms for the best case (a·n + b) and worst case (a·n² + b·n + c) are checked against the real counts for every n up to 150 and against arbitrary constants c₁…c₇. The average case is checked exactly over all n! orderings:

Input size → what is feasible: counting runs the algorithm itself, so use n ≤ 10⁴ (Θ(n²) = 10⁸ steps ≈ 1 s) for random or reversed input and n ≤ 8 for the all-orderings average (8! = 40,320 permutations; n = 12 would be 4.8·10⁸ permutations).

We focus on the worst case almost everywhere in this track, for three reasons: it's a guaranteed upper bound (never worse than promised), for some algorithms the worst case happens fairly often (e.g. searching for something absent), and the average case is frequently just as bad asymptotically as the worst case anyway (as with insertion sort: both are Θ(n²)). When comparing algorithms we also drop constant factors and lower-order terms and keep only the leading term's order of growth — e.g. an² + bn + c is simply written Θ(n²). The full machinery for this (O, Θ, Ω) is the next lesson in this track (growth of functions).

4. Selection sort & bubble sort

Selection sort is like repeatedly rummaging through the whole remaining pile of cards to find the single smallest one, then placing it at the front of your sorted row — every single time, even if the pile happens to already be in order. Bubble sort is like repeatedly sweeping left to right across a row of cards, swapping any two neighbours that are out of order, so that on each sweep the largest remaining card "bubbles" all the way to its final spot at the end.

selectionSort: for each position i from 0 to n−2, scan a[i..n−1] for its minimum and swap it into position i.

Edge case — an already sorted array: selection sort still scans every remaining element, so it does the same n(n−1)/2 comparisons and never needs a swap.

Try your own array (selection sort):

Input size → what is feasible: always exactly n(n−1)/2 comparisons: n = 5·10³ → 1.25·10⁷ (instant), n = 10⁵ → 5·10⁹ (too slow). Its advantage is at most n − 1 swaps.

Selection sort's inner scan always examines every remaining element, no matter how the input is arranged — there's no early exit even when the array is already sorted. That means its best case is also Θ(n²), unlike insertion sort, whose best case (already sorted) is Θ(n). Fewer swaps overall (at most n−1 total), but no better in the worst case.

bubbleSort in pseudocode — each pass sweeps left to right, so the largest remaining value ends up at the end of the unsorted part:

bubbleSort(a)

Edge case — an already sorted array and one with duplicates (the strict test a[j] > a[j + 1] never exchanges equal neighbours, which is why bubbleSort is stable):

Try your own array (bubbleSort):

Input size → what is feasible: Θ(n²): n ≤ 5·10³ is fine (1.25·10⁷ comparisons); never use it for n ≥ 10⁵. With the early-exit flag, already-sorted input of any size costs only n − 1 comparisons.

Both selection sort and bubble sort are Θ(n²) in the worst case, like insertion sort — but insertion sort is usually preferred among the three because its best case is linear and it does the least data movement on nearly-sorted input (its running time is Θ(n + D) where D is the number of inversions, defined in the last section below).

5. Divide and conquer: merge

Imagine two players each holding their own pile of cards, already sorted face-up in a row, smallest on the left. To merge them into one sorted row, you compare only the two leftmost, still-unplayed cards — one from each pile — and always play the smaller one onto a new row. Repeat until both piles are empty. You never need to look deeper into either pile, because everything behind the leftmost card in a sorted pile is only bigger.

Divide and conquer solves a problem by: Divide it into smaller subproblems of the same kind, Conquer the subproblems by solving them recursively (or directly, if small enough), then Combine the subproblem solutions into the solution for the original problem. Merge sort's Combine step is the merge procedure — it assumes a[p..q] and a[q+1..r] are already individually sorted and combines them into one sorted a[p..r]:

merge(a, p, q, r)

The trick that keeps the code simple: copy each run into its own array, then append a sentinel ∞ (a value bigger than anything real) to the end of both. Because ∞ can never actually win a comparison, the main loop (lines 5–11) never needs a separate "did a run run out yet?" check — once a run is exhausted, its sentinel simply loses every remaining comparison, and the other run's real values flow through untouched.

Edge case — one run is entirely smaller than the other, so the left run empties first and its sentinel ∞ has to lose every remaining comparison:

Try your own two sorted runs (note the tie rule left[i] ≤ right[j]: with equal values the left one is copied first):

Input size → what is feasible: one merge call is Θ(r − p + 1): merging two runs of 10⁶ elements is ~2·10⁶ steps (a few ms) and needs 2·10⁶ + 2 extra slots; the sentinel needs every real value < 2⁶² (the sentinel-free version below has no such limit).

You can also write merge without sentinels: copy both runs out as before, but this time the copying loop runs only while both pointers are still in range, and stops the instant either run is exhausted — then one final loop copies whatever is left of the other run (its remaining elements are already known to be the largest, since the other run is fully consumed). Both versions do the same Θ(n) work; the sentinel version just avoids writing that extra "copy the leftovers" loop.

6. mergeSort

mergeSort applies divide and conquer directly: split the array in half, recursively sort each half, then merge the two sorted halves.

mergeSort(a, p, r)

An edge case worth seeing explicitly — a subarray so small it never needs to divide at all, plus duplicate values (merge's left[i] ≤ right[j] test, not <, is what keeps duplicates stable — the left run wins ties):

Try your own array (comma-separated whole numbers, up to 9 values):

Input size → what is feasible: Θ(n lg n) always: n = 10⁶ → ≈ 2·10⁷ comparisons (~0.2 s); n = 10⁷ → ≈ 2.3·10⁸ (a few seconds); recursion depth ⌈lg n⌉ ≤ 24, so no stack problem. Compare insertion sort: n = 10⁶ would be ~2.5·10¹¹ shifts.

Dart implementation, matching mergeSort and merge line for line — p, q, r are indices into the same array, with both ends included:

A common bug when writing mergeSort in Dart: writing final q = (p + r) / 2; in Dart, which produces a double — Dart requires integer division here, written ~/ (matching ⌊(p+r)/2⌋, which always rounds down). Using / is a compile-time type error if p and r are later used as list indices expecting int.

mergeSort is not in-place (merge needs Θ(n) auxiliary space for the L and R arrays) but IS stable, and its running time is Θ(n lg n) in every case — best, worst, and average are all the same order of growth, unlike insertion sort.

7. Analyzing mergeSort: the recursion tree

Picture the array being split in half, then each half split in half again, and so on, drawn as an upside-down tree: the root is the whole array, its two children are the two halves, and so on down to single elements at the leaves. The recursion-tree method adds up the work done at every level of this tree, then adds the levels together.

mergeSort's recurrence is T(n) = 2T(n/2) + Θ(n) — two recursive calls on half-sized subproblems, plus Θ(n) to merge. Drawing the recursion tree: at level i there are 2ⁱ subproblems, each of size n/2ⁱ, and merging all of them at that level costs 2ⁱ × c·(n/2ⁱ) = cn — the same total, cn, at every level. Taking n to be a power of 2 (a simplifying assumption for this picture; for other n the sizes round and the tree has ⌈lg n⌉ + 1 levels), the tree has exactly lg n + 1 levels (it stops when subproblem size hits 1), so:

T(n) = cn · (lg n + 1) = cn·lg n + cn = Θ(n lg n)

As code: the recurrence as recursion + memo, its closed form n·lg n + n for n = 2^k (so T(8) = 8·3 + 8 = 32), the level-by-level sizes of the recursion tree (each level sums to n; ⌈lg n⌉ + 1 levels), and the real comparison count of mergeSort against the bound:

Input size → what is feasible: mergeSortT with memo is Θ(lg n) calls — n up to 2⁶² is fine; levelSizes materialises ~2n numbers, so keep n ≤ 10⁶.

Θ(n lg n) beats Θ(n²) for large n — this is exactly why merge sort scales better than insertion sort as arrays grow, even though insertion sort can win on small or nearly-sorted arrays (see the crossover-point question in the interview bank). A later lesson generalizes this recursion-tree technique to any recurrence, and the growth-of-functions lesson makes "Θ" itself precise.

How fast the gap opens — the ratio n² / (n lg n) = n / lg n:

n	n²	n lg n	n² ÷ (n lg n)
10	100	33.2	3.01
100	10,000	664.4	15.05
1,000	1,000,000	9,965.8	100.34
1,000,000	10¹²	19,931,569	50,171.7

And with constants, the crossover n₀ where c₂·n·lg n first drops below c₁·n² (no closed form, so it is searched — e.g. 50 n lg n beats n² from n = 439 on):

Input size → what is feasible: each evaluation is O(1); with c₂/c₁ ≤ 10⁴ the crossover is below 1.8·10⁵, so the scan (limit 10⁶) ends within milliseconds.

8. Binary search

Looking up a name in a printed directory, you don't scan page by page — you open to the middle, see whether your name comes before or after that page, and throw away the half you don't need. Repeat on the remaining half. Binary search does exactly this on a sorted array.

Binary search finds a value in a sorted array in Θ(lg n) time: check the middle element; if it's the target, done; if the target is smaller, recurse on the left half; if larger, recurse on the right half. Each check throws away half the remaining candidates, so after k checks only n/2^k elements remain — reaching 1 remaining element takes k = lg n checks.

Try it (enter a sorted, comma-separated list and a target to search for):

Edge case — a target that is absent (the window shrinks to empty). Edit the input to try a single-element array too, e.g. 7; 7:

Input size → what is feasible: Θ(lg n): n = 10⁷ sorted → ≤ 24 probes per query; the recursive version uses ≤ 24 stack frames. Needs sorted input (sorting once is Θ(n lg n)).

Binary search requires the array to already be sorted — it doesn't work on arbitrary input. Its Θ(lg n) running time is why sorting first (Θ(n lg n), one time) and then searching repeatedly (Θ(lg n) each) beats doing n linear searches (Θ(n) each) whenever there will be more than a handful of searches.

9. Horner's rule

To compute a polynomial like 3 + 2x + 5x², the naive way recomputes x² from scratch as a separate multiplication chain. Horner's rule instead factors the polynomial as 3 + x(2 + x(5)) — working from the innermost parentheses outward, each step is just "multiply what I have so far by x, then add the next coefficient." No powers of x are ever computed separately.

horner(a, x) — a[i] is the coefficient of xⁱ, i = 0..n

Edge case — a constant polynomial (degree n = 0, the loop runs once) and your own coefficients (zero coefficients and negative x are fine):

Input size → what is feasible: degree n = 10⁶ → 10⁶ multiplications with Horner versus (n+1)(n+2)/2 ≈ 5·10¹¹ for the naive method (too slow). Values are exact only while |p(x)| < 2⁶³ ≈ 9.2·10¹⁸ for Dart native int (use doubles, BigInt or a modulus beyond that).

The naive method computes xⁱ for each of the n+1 terms by repeated multiplication, costing Θ(i) work per term and Θ(n²) total. Horner's rule does exactly one multiply and one add per coefficient — Θ(n) total, and its correctness follows from the loop invariant y = Σ_k=0^n−(i+1) a_k+i+1x^k (at the start of the iteration for index i, y already holds the correct partial evaluation of the coefficients processed so far).

10. Counting inversions

An inversion is a pair of elements that are "out of order" relative to each other — like two people in a queue standing in the wrong relative order by height. The array [4, 1, 6, 3, 2] has 6 inversions: (4,1), (4,3), (4,2), (6,3), (6,2), (3,2) — every pair (i, j) with i < j but a[i] > a[j].

Counting inversions the obvious way checks every pair — Θ(n²). A smarter method gets Θ(n lg n) by piggy-backing on merge sort: whenever merge takes an element from the right run instead of the left, every element still waiting in the left run is bigger than it (the left run is sorted) — so that one pick creates exactly (elements still left in the left run) new inversions, all at once, for free, as a side effect of the merge that was happening anyway.

Edge case — the reverse-sorted array has the maximum n(n−1)/2 inversions; then try your own (equal values are not inversions):

Input size → what is feasible: n ≤ 3·10³ → brute force n²/2 ≈ 4.5·10⁶ pairs is instant; n = 2·10⁵ → 2·10¹⁰ pairs is too slow, the Θ(n lg n) merge-sort counter needs ≈ 3.5·10⁶ steps. The count itself can reach n(n−1)/2 ≈ 2·10¹⁰, which overflows a 32-bit int but not Dart's 64-bit int.

A reverse-sorted array of length n has the maximum possible n(n−1)/2 inversions (every pair is out of order); a sorted array has 0. Insertion sort's exact running time is Θ(n + D) where D is the number of inversions — which is why insertion sort is a great choice specifically for nearly-sorted input (small D), even though its worst case is Θ(n²).

Quiz

Interview questions

Cheat sheet

Algorithm	Best	Avg	Worst	Space	Stable?	In-place?	Use when…
Insertion sort	Θ(n)	Θ(n²)	Θ(n²)	O(1)	Yes	Yes	Small n, or nearly-sorted data (Θ(n+D), D = inversions)
Selection sort	Θ(n²)	Θ(n²)	Θ(n²)	O(1)	No*	Yes	Minimizing the number of swaps matters more than comparisons
Bubble sort	Θ(n²)†	Θ(n²)	Θ(n²)	O(1)	Yes	Yes	Teaching / simplicity only — rarely used in practice
Merge sort	Θ(n lg n)	Θ(n lg n)	Θ(n lg n)	Θ(n)	Yes	No	Guaranteed Θ(n lg n) needed, or sorting linked lists / external data
Binary search	Θ(1)	Θ(lg n)	Θ(lg n)	O(1)	—	—	Repeated lookups on already-sorted data
Horner's rule	Θ(n) (vs Θ(n²) naive)			O(1)	—	—	Evaluating a degree-n polynomial at a point

*Selection sort's naive array swap is not stable in general (a stable variant exists by inserting instead of swapping, at extra cost). †Bubble sort's best case becomes Θ(n) only with an added early-exit flag when a full pass makes no swaps — the plain pseudocode shown above has no such flag.