Two sorting algorithms, one proof technique, and the analysis vocabulary that the remaining thirty-three chapters assume you own.
Chapter 2 is where CLRS stops describing and starts doing. It presents insertion sort and proves it correct with a loop invariant; it sets up the RAM model and analyses insertion sort line by line to get the Θ(n²) worst case; then it introduces divide-and-conquer and derives merge sort, whose Θ(n lg n) cost comes out of a recurrence. Three techniques — invariants, line-by-line counting, and recurrences — get used constantly from here on. This is the chapter to reread if the later analysis ever feels like hand-waving.
INSERTION-SORT(A, n) rather than relying on A.length. And MERGE no longer uses ∞ sentinels; it checks the indices directly, which is both closer to how you would really write it and easier to reason about at the boundaries. Array slices are written A[p:r].The chapter restates the sorting problem from Chapter 1, then adds a piece of vocabulary that matters in practice. The numbers being sorted are called keys, and in a real program a key rarely travels alone — it is attached to satellite data, and the key plus its satellite data forms a record. When CLRS shows an algorithm moving a key, understand it as moving the whole record, or a pointer to it. That detail decides whether a swap costs a few bytes or a few kilobytes, and it is why real implementations sort arrays of pointers.
Two things about that analogy are exactly right. The sorted region grows by one element per round, and inserting means shifting the larger elements up to open a gap, not swapping repeatedly. Here it is in the book’s notation. The algorithm sorts in place: it rearranges A itself, using only a constant amount of extra storage.
INSERTION-SORT(A, n)
1 for i = 2 to n
2 key = A[i]
3 // Insert A[i] into the sorted subarray A[1:i-1].
4 j = i - 1
5 while j > 0 and A[j] > key
6 A[j+1] = A[j]
7 j = j - 1
8 A[j+1] = keyEight lines. The outer loop chooses the next element to place; the inner loop opens the gap by sliding larger elements one position right.
Read the inner loop carefully, because two details are easy to get wrong when you rewrite this from memory:
j > 0 is tested before A[j] > key. CLRS pseudocode short-circuits and, so when j reaches 0 the second test is never evaluated and A[0] is never read. Swap the two conditions and you index outside the array on any element that belongs at the front.key is held in a register the whole time, so the loop only ever moves one value per iteration. Line 8 drops key into the gap once the loop stops.Note also that the loop starts at i = 2, not 1. A single element is already sorted, so there is nothing to do for A[1]. CLRS indexes arrays from 1.
⟨5, 2, 4, 6, 1, 3⟩. The blue boundary moves right by exactly one position per iteration of the outer loop, and everything to its left is sorted. At i = 4 the key 6 is already in place, so the inner loop never runs.Figure 2.1 is worth walking through slowly once, because every claim in the correctness proof is visible in it.
i = 2: key = 2. The inner loop compares against 5, shifts it right, then stops because j hits 0. key lands at position 1.i = 4: key = 6, and A[3] = 5 is not greater than 6, so the while test fails immediately. Line 8 writes key back where it came from. Zero shifts — this is the cheap case, and it is what makes insertion sort linear on already-sorted input.i = 5: key = 1 is smaller than everything before it, so all four elements shift right and j runs all the way to 0. Four shifts — this is the expensive case.The pattern to notice: the cost of one outer iteration is the number of elements the key has to travel past. Sum that over all i and you have the running time, which is exactly the analysis in §2.2.
The trace makes insertion sort look obviously right, but “obviously” is not a proof, and correctness is a claim about every input. The tool CLRS introduces here, and uses for the rest of the book, is the loop invariant: a property that holds before and after every iteration of a loop, chosen so that when the loop finally stops, the property gives you what you wanted.
for loop of lines 1–8, the subarray A[1:i-1] consists of the elements originally in A[1:i-1], but in sorted order.To use an invariant as a proof you must establish three things. CLRS names them, and the names are worth memorising because the book uses them verbatim in every later proof.
| Property | What you must show | For INSERTION-SORT |
|---|---|---|
| Initialization | The invariant is true before the first iteration. | Before the first iteration i = 2, so A[1:i-1] is A[1:1] — a single element, which is the original element and is trivially sorted. |
| Maintenance | If it is true before an iteration, it remains true before the next one. | The body shifts A[i-1], A[i-2], … right by one while they exceed key, then places key in the gap. The result is that A[1:i] holds the original elements of A[1:i] in sorted order. Incrementing i restores the invariant for the next iteration. |
| Termination | When the loop ends, the invariant plus the reason it ended gives you the result you want. | The loop ends when i > n, that is i = n+1. Substituting into the invariant: A[1:n] consists of the original elements in sorted order. That is the entire array, so the algorithm is correct. |
1, 2, 3, …. Getting the invariant exactly strong enough, and no stronger, is the real skill; the proof is mechanical afterwards.Strictly, a full proof also needs an invariant for the inner while loop — something like “A[j+2:i] holds the original elements of A[j+1:i-1], all of them greater than key”. CLRS leaves that as an exercise. In practice, proving the outer loop and arguing the inner one informally is what most people do, and it is what the book models here.
CLRS pseudocode is not any real language, and a few of its conventions trip up readers who assume C or Python semantics. The ones that actually change meaning:
| Convention | What it means |
|---|---|
| Indentation shows block structure | There are no braces and no end keywords. The body of a loop or conditional is whatever is indented under it — the same rule Python later adopted. |
| Arrays are 1-indexed | A[1] is the first element, A[n] the last. Off-by-one differences against 0-indexed code are expected; translate deliberately. |
A[p:r] is a slice | The subarray from index p through r inclusive, unlike Python where the endpoint is excluded. New notation in the 4th edition. |
= assigns, == compares | And i = j = e assigns e to both, evaluated right to left. |
and and or short-circuit | Evaluate left to right and stop as soon as the answer is determined. Line 5 of insertion sort depends on this for its bounds safety. |
| The loop counter survives the loop | After for i = 2 to n finishes, i equals n+1. The termination argument above uses this directly. |
| Variables are local | Unless stated otherwise, so no accidental globals. |
| Objects are references | Attributes are written x.attr. Assigning y = x makes y.attr and x.attr the same field. Parameters are passed by value, but for an object that means the pointer is copied, so mutations are visible to the caller. |
NIL is the null pointer | Used throughout the tree and list chapters. |
| Error handling is omitted | Deliberately. It would obscure the algorithm, which is what the pseudocode exists to communicate. |
Before you can say how long an algorithm takes, you have to say what machine it runs on. If the model is too vague the analysis is meaningless; if it is too detailed the analysis is impossible. CLRS uses the random-access machine (RAM), a deliberate middle point.
| The RAM model assumes | Why the assumption is there |
|---|---|
| One processor, instructions executed one at a time, no concurrency | Keeps the count a single number. Chapter 26 relaxes this. |
| Each primitive instruction takes a constant amount of time | Arithmetic, comparison, data movement, control flow. Constants may differ between instruction types, but none depends on the operand values. |
| Data types are integer, floating point, and character | Matches real hardware closely enough. |
Each word holds c lg n bits for input size n, with c ≥ 1 | This is the subtle one, explained below. |
| Memory access costs the same regardless of address | “Random access.” No cache hierarchy in the model. |
The word-size assumption deserves a moment. It has to be at least lg n bits, or you could not even hold an index into the input. But it must be bounded above too, because if a word could be arbitrarily large you could pack the entire input into one word and perform absurd operations in “constant time”, which would make the model useless. c lg n for a constant c is the compromise: big enough to be realistic, small enough to prevent cheating.
Θ notation is a guide rather than a verdict. Keep it in mind and the model will not mislead you.Two more definitions the chapter pins down:
n. For multiplying two integers, it is the total number of bits needed to represent them. For a graph, it is usually two numbers, the vertex count and the edge count.i of the pseudocode is charged a constant cᵢ per execution.Now count. Let tᵢ denote the number of times the while loop test on line 5 is executed for that value of i. Each line costs a constant per execution, and the total is the sum of cost times count.
| Line | Statement | Cost | Times executed |
|---|---|---|---|
| 1 | for i = 2 to n | c₁ | n |
| 2 | key = A[i] | c₂ | n - 1 |
| 3 | // comment | 0 | n - 1 |
| 4 | j = i - 1 | c₄ | n - 1 |
| 5 | while j > 0 and A[j] > key | c₅ | ∑ from i=2 to n of tᵢ |
| 6 | A[j+1] = A[j] | c₆ | ∑ from i=2 to n of (tᵢ - 1) |
| 7 | j = j - 1 | c₇ | ∑ from i=2 to n of (tᵢ - 1) |
| 8 | A[j+1] = key | c₈ | n - 1 |
Three counts are worth checking rather than accepting. Line 1 runs n times, not n-1, because the loop test is evaluated one extra time to discover that i has passed n. Lines 6 and 7 run tᵢ - 1 times rather than tᵢ, because the last evaluation of the line 5 test is the one that fails and exits the loop. And line 3 is a comment, costing nothing — it is listed only to keep the line numbers honest.
The running time is the sum over lines of cost × times:
T(n) = c₁n + c₂(n-1) + c₄(n-1) + c₅·∑tᵢ + c₆·∑(tᵢ-1) + c₇·∑(tᵢ-1) + c₈(n-1)Everything now depends on the tᵢ, and those depend on the input, not just its size. That is the whole reason the next section exists.
If A is already in sorted order, then for every i the test A[i-1] > key fails on the first try, so tᵢ = 1 and lines 6 and 7 never execute. Substituting:
T(n) = c₁n + (c₂ + c₄ + c₅ + c₈)(n - 1)
= (c₁ + c₂ + c₄ + c₅ + c₈)·n - (c₂ + c₄ + c₅ + c₈)
= an + b for constants a, b that depend on the cᵢ
= Θ(n)A linear function of n. Insertion sort on sorted input does a single pass, confirming each element is already in place.
Now every key must travel past every element before it. For each i, the inner loop runs until j hits 0, so it executes the test tᵢ = i times. Two summations are needed, and both are standard:
∑ from i=2 to n of i = n(n+1)/2 - 1
∑ from i=2 to n of (i - 1) = n(n-1)/2The first is the arithmetic series 1 + 2 + … + n with the i = 1 term removed. The second is 1 + 2 + … + (n-1). Appendix A collects these.
Substituting gives a quadratic:
T(n) = (c₅/2 + c₆/2 + c₇/2)·n²
+ (c₁ + c₂ + c₄ + c₅/2 - c₆/2 - c₇/2 + c₈)·n
- (c₂ + c₄ + c₅ + c₈)
= an² + bn + c for constants a, b, c
= Θ(n²)CLRS gives three reasons for concentrating on the worst case, and they are the reasons the whole field does:
Suppose the input is a randomly chosen permutation. To insert A[i], on average half of the i-1 elements in A[1:i-1] are greater than it, so tᵢ is about i/2. Halving each term halves the sum, so the leading coefficient shrinks by a factor of two — and a quadratic with a smaller constant is still a quadratic:
Θ(n²), the same order of growth as the worst case. Being twice as fast on typical input does not rescue a quadratic algorithm.CLRS is careful with the vocabulary here. An average-case analysis assumes a probability distribution over inputs, which you may not know. An expected running time is the average over the algorithm’s own random choices, which you control because you built the randomness in. That distinction becomes the subject of Chapter 5, and it is the difference between hoping your input is not adversarial and guaranteeing it does not matter.
Look at what happened in both derivations. Real constants c₁ through c₈ were carried through several lines of algebra and then thrown away, leaving Θ(n) and Θ(n²). The chapter makes that abstraction official:
n, and we ignore the leading term’s constant coefficient, since constant factors are less significant than the rate of growth.Two simplifications, both justified by letting n grow:
| Discarded | Because | Example |
|---|---|---|
| Lower-order terms | Their share of the total shrinks to nothing as n grows | At n = 1000, bn is a thousandth of an² when a = b |
| The leading constant | It is a fixed multiplier, so it shifts the curve but never changes its shape | Chapter 1’s Computer A had a 1000× constant advantage and still lost |
We therefore say insertion sort has a worst-case running time of Θ(n²), and we call one algorithm more efficient than another if its worst-case running time has a lower order of growth. Because of the constants, that judgement can be wrong for small inputs — and is, as Chapter 1’s table showed — but it is right for large ones, and large ones are where the time goes.
O, Ω, and Θ. Everything in this section is legitimate; it is simply stated loosely here so the sorting can proceed.Insertion sort is incremental: having sorted A[1:i-1], it inserts one more element to get A[1:i]. Section 2.3 introduces the alternative that produces most of the fast algorithms in the book.
| Step | In general | In merge sort |
|---|---|---|
| Divide | Split the problem into subproblems that are smaller instances of the same problem | Split the n-element subarray into two halves of n/2 elements each |
| Conquer | Solve the subproblems recursively; if a subproblem is small enough, solve it directly as a base case | Sort each half by recursive calls; a subarray of length 1 is already sorted |
| Combine | Assemble the subproblem solutions into a solution for the original | Merge the two sorted halves into one sorted subarray |
The recursion has to stop, which is what the base case is for. In merge sort the base case is a subarray of length 1 or less: nothing to do, because a one-element sequence is already in sorted order. The problem shrinks strictly on every call, so the base case is always reached.
The combine step is where all the work happens, and it is worth understanding on its own before looking at the recursion. MERGE(A, p, q, r) assumes A[p:q] and A[q+1:r] are each already sorted, and merges them into a single sorted A[p:r]. The indices must satisfy p ≤ q < r.
MERGE(A, p, q, r)
1 nL = q - p + 1 // length of A[p:q]
2 nR = r - q // length of A[q+1:r]
3 let L[0:nL-1] and R[0:nR-1] be new arrays
4 for i = 0 to nL - 1 // copy A[p:q] into L
5 L[i] = A[p + i]
6 for j = 0 to nR - 1 // copy A[q+1:r] into R
7 R[j] = A[q + j + 1]
8 i = 0 // smallest remaining element in L
9 j = 0 // smallest remaining element in R
10 k = p // location in A to fill
11 // While both L and R still have unmerged elements,
12 // copy the smaller one back into A[p:r].
13 while i < nL and j < nR
14 if L[i] ≤ R[j]
15 A[k] = L[i]
16 i = i + 1
17 else
18 A[k] = R[j]
19 j = j + 1
20 k = k + 1
21 // One of L, R is exhausted. Copy the remainder of the other.
22 while i < nL
23 A[k] = L[i]
24 i = i + 1
25 k = k + 1
26 while j < nR
27 A[k] = R[j]
28 j = j + 1
29 k = k + 1The 4th edition version. Note L and R are indexed from 0 while A is indexed from 1 — deliberate, and a common source of confusion when transcribing.
MERGE appended a sentinel of ∞ to the end of both L and R, which guaranteed the main loop could always compare two real values and let it run for exactly r - p + 1 iterations with no cleanup loops. It is elegant, but it requires a value larger than every key, which is awkward in real code. The 4th edition drops sentinels and pays for it with the two tidy-up loops on lines 22–29. Same cost, fewer assumptions.Three points worth checking:
L and R at all? Because the output is being written back into the same region of A that the input occupies. Without the copies, writing A[k] would clobber input you have not read yet. This is why merge sort is not in place and needs Θ(n) extra space — the one real cost against insertion sort.i = nL or j = nR. Whichever array was exhausted has a loop that runs zero times.≤ on line 14 makes the sort stable. On a tie it takes from L, the left half, which held the earlier elements. Equal keys therefore keep their original relative order. Change it to < and you lose stability while everything else still works.Cost. Lines 1–3 and 8–10 are constant. The copy loops run nL and nR times. Each iteration of any of the three merge loops places exactly one element into A and never removes one, so across all of them exactly n = r - p + 1 elements are placed, at constant cost each. Total: Θ(n). That linear combine step is what makes the whole recursion work.
CLRS proves MERGE correct with the same three-property method. The invariant for the main loop of lines 13–20:
A[p:k-1] contains the k - p smallest elements of L and R, in sorted order. Moreover, L[i] and R[j] are the smallest elements of their arrays that have not been copied back into A.k = p, so A[p:k-1] is empty and contains the 0 smallest elements. With i = j = 0, L[0] and R[0] are indeed the smallest uncopied elements of their arrays.L[i] ≤ R[j]. Then L[i] is the smallest element not yet copied back, and since A[p:k-1] holds the k-p smallest, appending L[i] makes A[p:k] hold the k-p+1 smallest. Incrementing i and k restores the invariant. The else branch is symmetric.i = nL or j = nR. The invariant says A[p:k-1] holds the k-p smallest elements in order; the remaining elements of whichever array is not exhausted are all larger and already sorted, so the cleanup loops append them correctly.With MERGE as the combine step, merge sort itself is six lines.
MERGE-SORT(A, p, r)
1 if p ≥ r // zero or one element?
2 return
3 q = ⌊(p + r) / 2⌋ // midpoint of A[p:r]
4 MERGE-SORT(A, p, q) // recursively sort A[p:q]
5 MERGE-SORT(A, q+1, r) // recursively sort A[q+1:r]
6 MERGE(A, p, q, r) // merge the two sorted halvesCall it as MERGE-SORT(A, 1, n) to sort the whole array. Lines 1–2 are the base case, line 3 divides, lines 4–5 conquer, line 6 combines.
The recursion is easiest to see as a picture. The array splits until every piece has one element, then merges back up, and each merge produces a sorted run twice as long as its inputs.
⟨5, 2, 4, 7, 1, 3, 2, 6⟩, viewed bottom-up. The divide phase runs the other way, splitting until each piece holds one element. Every level does Θ(n) total work merging, and there are lg n + 1 levels.Divide-and-conquer running times are naturally described by recurrences, because the algorithm is defined in terms of itself. Let T(n) be the worst-case time to sort n elements. Read it off the pseudocode:
Θ(1).n/2: 2T(n/2).n elements: Θ(n).The divide term is dominated by the combine term, so the two collapse into Θ(n):
╱ Θ(1) if n = 1
T(n) = │
╱ 2T(n/2) + Θ(n) if n > 1CLRS notes that the split is really into ⌈n/2⌉ and ⌊n/2⌋, and that ignoring the floors and ceilings does not change the answer. Chapter 4 justifies that shortcut properly.
Θ(n lg n)The cleanest argument is the recursion tree. Rewrite the Θ(n) as cn for some constant c, then expand.
T(n) = 2T(n/2) + cn. Subproblems halve in size but double in number, so every level costs the same cn. Multiply by the number of levels and you have the answer.The argument in three steps:
cn. At depth d there are 2ᵈ subproblems, each of size n/2ᵈ, each costing c · n/2ᵈ. The 2ᵈ cancels the 1/2ᵈ, leaving cn at every level. This is the crux — the doubling of subproblem count exactly offsets the halving of subproblem size.lg n + 1 levels. The size sequence n, n/2, n/4, … reaches 1 after lg n halvings, and counting the root level gives lg n + 1.cn(lg n + 1) = cn lg n + cn. Dropping the lower-order term and the constant gives Θ(n lg n).Θ(n lg n) for this recurrence in one step.| Insertion sort | Merge sort | |
|---|---|---|
| Strategy | Incremental | Divide-and-conquer |
| Best case | Θ(n), on sorted input | Θ(n lg n), always |
| Worst case | Θ(n²), on reverse-sorted input | Θ(n lg n), always |
| Average case | Θ(n²) | Θ(n lg n) |
| Extra space | Θ(1) — sorts in place | Θ(n) — the L and R copies |
| Stable | Yes | Yes, because of the ≤ on line 14 |
| Constant factor | Small | Larger, from recursion and copying |
| Wins when | n is small, or data is nearly sorted | n is large |
Merge sort beats insertion sort asymptotically and loses on constants and space. That is why real library sorts are hybrids: recurse like merge sort or quicksort while the subarray is large, then switch to insertion sort once it drops below a threshold of a few dozen elements. CLRS makes this an exercise (2-1), and it is the standard trick in production implementations.
Θ(n) best case and Θ(n²) worst and average.c lg n-bit words, uniform memory access. It ignores caches, which is why asymptotics guide rather than decide.Θ(n) scratch space.lg n + 1 levels costs cn, because subproblems double in number as they halve in size. Hence Θ(n lg n).Chapter 3 makes the notation honest. “Drop the lower-order terms and the constant” becomes the formal definitions of O, Ω, and Θ, along with o and ω, so that statements like “insertion sort is Θ(n²) in the worst case” can be proved rather than asserted. Chapter 4 then returns to the recurrence T(n) = 2T(n/2) + Θ(n) and gives you three general methods for solving recurrences, so you never have to invent the tree argument again.