Algorithms and Data Structures

A program that returns the right answer can still be worthless, and nothing in an introductory programming course gives you a way to say so.

Two correct programs

Here is a task with no ambiguity in it. Given a list of $n$ numbers, say whether any value appears twice. Both of the following solve it, and both are correct in the sense that they return the right answer on every input.

The first compares every element with every later element. For a list of six numbers that is five comparisons involving the first element, four more involving the second, and so on down to one, which is fifteen comparisons in total. In general it is $n(n-1)/2$: for a hundred numbers, 4950 comparisons; for a million, 499,999,500,000.

The second sorts the list first and then walks it once, checking each element against its neighbour. Sorting a million numbers well takes roughly $n{\log }_{2}n$ comparisons, about 19.9 million, and the walk adds a million more. Call it 21 million against 500 billion.

If the machine performs a billion comparisons a second, and both programs are otherwise identical in every respect, the first finishes in about eight minutes and the second in about a fiftieth of a second. The ratio at a million items is roughly 25,000. Push the input to a hundred million and the ratio passes 1.8 million: two and a half seconds against nearly two months.

Nothing in the previous course could distinguish those two programs. Correctness is a property they share. The difference between them is a property nobody has yet named, and this lesson names it: cost, meaning how the resources a program consumes grow as its input grows. The whole subject is the study of that quantity, because it is the only property of a program, apart from correctness, that survives being ported to a different machine.

The stopwatch measures the machine

The obvious way to measure cost is to run the program and time it. This is a real measurement and it is worth doing, but on its own it answers the wrong question.

Suppose you time the nested-loop version on a laptop and it takes 5.0 seconds on 100,000 numbers. What have you learned? That number depends on the processor's clock speed, on how much of the array fitted in cache, on whether the language was compiled or interpreted, on whether a browser was updating in the background, and on how many times the just-in-time compiler had already seen that loop. Move to a machine twice as fast and it becomes 2.5 seconds. Rewrite the same algorithm in C and it might become 0.8 seconds. None of those changes tell you anything about the algorithm, because the algorithm never changed.

Worse, the stopwatch answers only for the input you happened to try. Timing at $n=100\{,\}000$ does not tell you what happens at $n={10}^7$, and the whole reason to care is that inputs grow. A measurement that has to be repeated for every size and every machine is not a theory, it is a table.

What is wanted is a number attached to the algorithm rather than to the run: a count of the operations the algorithm performs, expressed as a function of the size of its input. Two things follow immediately. First, "operation" has to be pinned down, since the count is meaningless until you say what you are counting. Second, the count has to be a function of a single number $n$, which means deciding what "size" means.

A model of a machine

The standard idealisation is the RAM model, short for random access machine, and it is the model every complexity claim in this course is made against. It says: the machine has an unbounded array of memory cells, each holding one value; reading or writing any cell costs one step regardless of its address; and a fixed set of primitive operations on those values, arithmetic, comparison, assignment, and the jumps that implement control flow, each cost one step.

Under that model, counting is mechanical. A single assignment is one step. A loop body of $k$ steps run $m$ times is $km$ steps. Indexing a[i] is one step, whether i is 0 or 999,999.

The model is a lie in three specific places, and knowing where it lies is what stops you trusting it too far. It says all memory access costs the same, but real machines have caches, and a read that hits the fastest cache can be a hundred times quicker than one that goes to main memory. It says arithmetic on a value costs one step, which is true for machine-word integers and false for the thousand-digit numbers used in cryptography, where multiplication has its own cost function. And it counts steps rather than joules or bytes, so a program that is fast and needs an extra copy of the input looks free.

Nevertheless it is the right default. It is machine-independent, it is simple enough to count in, and its predictions about which of two algorithms wins at large $n$ are almost always right. Where it fails, later lessons say so explicitly: the memory hierarchy is exactly why B-trees exist, and space is exactly the price mergesort pays.

Counting steps against input size

Size means the number of things in the input: the length of the array, the number of vertices in a graph, the number of characters in a string. It is written $n$, and where two quantities matter independently, as with a graph's $V$ vertices and $E$ edges, both are named.

Take the nested-loop duplicate check and count it exactly. The outer loop runs with $i$ from $0$ to $n-2$. For each $i$, the inner loop runs with $j$ from $i+1$ to $n-1$, so it performs $n-1-i$ comparisons. The total is

If each pass of the inner loop costs a comparison, an increment and a bounds test, three steps, the program costs about $3n(n-1)/2$ steps plus a fixed amount of setup. Written out, $1.5n^2-1.5n+c$.

Example. How many comparisons does the nested-loop duplicate check perform on a list of 100 numbers, and on a list of 1000?

Substitute into $n(n-1)/2$. For $n=100$ that is $100\times 99/2=4950$. For $n=1000$ it is $1000\times 999/2=499\{,\}500$. The input grew by a factor of 10 and the work grew by a factor of about 101, which is the quadratic behaviour showing itself: the ratio approaches ${10}^2$ from above because of the $-n$ term.

Now you. How many comparisons does it perform on a list of 500 numbers? By what factor does that exceed the count for 100?

Three questions, not one

An exact count of $n(n-1)/2$ is unusually tidy, because that algorithm does the same work on every input of a given size. Most do not. Linear search, scanning an array from the front until the target is found, is the standard illustration.

If the target sits in the first cell, the search costs one comparison. If it sits in the last, or is absent, it costs $n$. So "the cost of linear search on $n$ elements" is not a single number, and pretending otherwise is how people end up surprised. There are three separate questions, and they have three separate answers.

The best case is the smallest cost over all inputs of size $n$: one comparison. It is nearly useless for prediction, because it describes the luckiest input rather than a typical one, and any algorithm can be made to look good on a case chosen for it.

The worst case is the largest cost over all inputs of size $n$: $n$ comparisons. It is the default in this course and in most of the literature, for two reasons. It is a guarantee, which is what you need when the program controls an aircraft or a trading system, and it is a claim about all inputs, so it needs no assumption about which inputs occur.

The average case is the expected cost over some distribution of inputs, and the phrase hides the important part: which distribution. Suppose the target is present and equally likely to be in any of the $n$ positions. The cost is $i$ comparisons when the target is at position $i$, each with probability $1/n$, so the expected cost is

about half the array. That number is only as good as the assumption. If the target is usually absent, every search costs $n$. If the data are requests to a web cache, where a few keys are asked for constantly, the average is far below $n/2$ and the uniform model is simply wrong. An average-case claim without a stated distribution is not a result.

Example. An array holds 1000 distinct values. Under the assumption that the searched-for value is present and equally likely to be at any position, what is the expected number of comparisons for linear search, and what is the worst case?

Expected cost is $(n+1)/2=1001/2=500.5$ comparisons. Worst case is $n=1000$, when the value is in the last cell. Note that the average is not half the worst case by coincidence: it is $(n+1)/2$ against $n$, a ratio approaching $1/2$ as $n$ grows.

Now you. The same array, but now half of all searches are for values that are not in the array at all, and the other half are for values uniformly placed within it. What is the expected number of comparisons?

What "size" means, exactly

One trap deserves naming early, because it recurs in the last lesson of this course.

Consider testing whether an integer $N$ is prime by trying every divisor from 2 up to $\sqrt{N}$. That is about $\sqrt{N}$ operations, which sounds cheap. For $N$ around ${10}^{18}$ it is ${10}^9$ divisions, a second or so.

But the input to that program is not $N$ things. It is the number $N$, written down, which takes about ${\log }_{2}N$ bits: 60 bits for ${10}^{18}$. So the input size is $b=60$, and the cost $\sqrt{N}=2^{b/2}$ is exponential in the size of the input. Adding two digits to $N$ multiplies the work by ten. At 200 digits, the numbers used in RSA, trial division would take longer than the age of the universe, and that is precisely why the method is safe to build a cryptosystem on.

The lesson is that $n$ counts symbols in the input, not the magnitude of a number in it. For arrays and graphs the two coincide and nobody thinks about it. For algorithms whose input is a number, they do not, and the distinction is exactly what separates a polynomial-time algorithm from an exponential one.

Example. How many divisions does trial division perform on $N={10}^{12}$, and how many bits long is that input?

The divisor runs up to $\sqrt{N}={10}^6$, so about a million divisions, which is instant. The input is ${\log }_2{10}^{12}=39.9$ bits, so 40 bits, and the cost ${10}^6$ is close to $2^{20}=2^{b/2}$ with $b=40$.

Now you. Repeat for $N={10}^{24}$.

Why exact counts do not survive

So the duplicate check costs $1.5n^2-1.5n+c$ steps. Now try to defend that expression to somebody with a different compiler.

The 1.5 came from a guess that a comparison, an increment and a bounds test cost one step each. On a real processor, the comparison and the test may fuse into one instruction, the increment may be free because it overlaps with a memory load, and the whole loop may be vectorised to handle four elements at once. The constant is not 1.5. It is not knowable without naming the machine, and once you name the machine you are back to timing.

The $-1.5n$ term is more solidly derived, since it comes from the arithmetic rather than the hardware. But look at what it contributes. At $n=1000$ the quadratic term is 1,500,000 and the linear term subtracts 1500, one part in a thousand. At $n={10}^6$ it is one part in a million. Any term of lower degree is invisible at the sizes where cost actually matters.

What is left after discarding the indefensible constant and the invisible lower terms is the shape: this cost grows like $n^2$. That single fact predicted the eight minutes against the fiftieth of a second at the start of this lesson, and it did so without knowing the machine. The next lesson makes "grows like" precise, with a definition that has explicit witnesses and can be proved rather than waved at, and then prices the resulting hierarchy of shapes in real seconds.

An exact step count is machine-specific and unusable, so the previous lesson ended by throwing away everything except the shape of the growth, and this lesson makes "shape" a definition rather than a gesture.

What the definition has to do

The claim to be formalised is "this cost grows like $n^2$". Three properties are wanted from it.

It must ignore constant factors, because the constants come from the hardware and the compiler and cannot be defended. It must ignore lower-order terms, because at the sizes where cost matters they contribute a vanishing fraction. And it must be provable, so that a claim can be settled rather than argued about.

The standard device does all three at once. Instead of asking whether two functions are equal, ask whether one is eventually bounded by a multiple of the other. "Eventually" throws away small $n$, which is where lower-order terms live. "A multiple of" throws away the constant. And both are witnessed by numbers you can write down, which makes the claim checkable.

The notation is Paul Bachmann's, from 1894, popularised in analysis by Edmund Landau and brought into computing by Donald Knuth in a 1976 note that fixed the definitions used here.

Big O: an upper bound

Let $f(n)$ and $g(n)$ be functions from positive integers to non-negative reals. Then

The pair $(c,n_0)$ is called a witness. To prove a big-O claim you produce one; to refute a claim you show no pair can exist. Nothing else is involved, and in particular no limits are needed.

The equals sign is an abuse of notation that everyone commits and nobody defends. $O(g)$ is really a set of functions, and $f=O(g)$ means $f\in O(g)$. The abuse is harmless as long as you never read it symmetrically: $n=O(n^2)$ is true and $O(n^2)=n$ is nonsense.

Example. Show that $3n^2+5n+100=O(n^2)$ by producing a witness.

The strategy is to bound each term by a multiple of $n^2$. For the middle term, $5n\le 0.5n^2$ whenever $n\ge 10$. For the constant, $100\le n^2$ whenever $n\ge 10$. So for all $n\ge 10$,

The witness is $c=4.5$, $n_0=10$. Check it at the boundary: $f(10)=300+50+100=450$ and $4.5\times 100=450$, so the inequality holds with equality there, and at $n=9$ it fails ($388>364.5$), which is why $n_0$ could not be smaller for this particular $c$. Witnesses are never unique: $c=108$, $n_0=1$ works too, and is just as valid a proof.

Now you. Produce a witness showing $2n^3+7n^2+3=O(n^3)$.

Omega and Theta: the other two bounds

Big O alone is a weak statement, because it is an upper bound and nothing stops it being loose. Every algorithm in this course is $O(2^n)$, and saying so tells you nothing. Two companions fix that.

$f(n)=\Omega (g(n))$ if there are $c>0$ and $n_0$ with $f(n)\ge cg(n)$ for all $n\ge n_0$: a lower bound, used to say an algorithm cannot do better than something, and used for problems rather than algorithms when proving that no algorithm can.

$f(n)=\Theta (g(n))$ if both hold: there are $c_1,c_2>0$ and $n_0$ with $c_{1}g(n)\le f(n)\le c_{2}g(n)$ for $n\ge n_0$. This is the tight statement, and it is what "grows like" actually means.

So $3n^2+5n+100$ is $\Theta (n^2)$: the upper witness is above, and for the lower, $3n^2+5n+100\ge 3n^2$ for every $n\ge 1$, giving $c_1=3$, $n_0=1$. It is also $O(n^3)$, truthfully but uselessly, and it is not $\Theta (n^3)$, because no $c_1>0$ has $3n^2+5n+100\ge c_1{n}^3$ eventually: divide by $n^3$ and the left side goes to zero while $c_1$ does not.

Refutations work the same way, by contradiction on the witness. Is $n^2=O(n)$? Suppose a witness $(c,n_0)$ existed, so $n^2\le cn$ for all $n\ge n_0$. Divide by $n$: $n\le c$ for all $n\ge n_0$. But $n$ is unbounded, so take $n=\max (c,n_0)+1$ and the inequality fails. No witness exists.

Prefer $\Theta$ wherever you can prove it. Most published results are stated with $O$ out of caution, since an upper bound is what a guarantee needs, but when a source says an algorithm is $O(n\log n)$ and you want to know whether it might secretly be linear, the answer is usually that the author could have written $\Theta$ and chose the weaker word.

The hierarchy, priced

Definitions settle arguments; a table shows why anyone cares. Assume a machine performing ${10}^9$ steps per second, which is the right order of magnitude for a single core running simple loop code.

Read the columns rather than the rows. At $n=100$ every one of the polynomial costs is imperceptible, and choosing between them is a waste of a morning. At $n={10}^6$ the same choices are the difference between an instant response, a coffee break and a career.

The entry worth staring at is $2^n$. At $n=50$ an exponential algorithm running a billion steps a second takes thirteen days; at $n=60$ it takes 36.5 years. Ten more items, a factor of a thousand. Buying a machine a thousand times faster buys you ten more items. That is why the last lesson of this course treats exponential cost as a qualitative barrier rather than a large number.

Example. A quadratic algorithm costing exactly $n^2$ steps handles $n={10}^4$ in 0.1 seconds on a given machine. A colleague proposes running it on $n={10}^6$. How long will that take, and would a machine 100 times faster fix it?

Cost scales as $n^2$, and $n$ grew by a factor of 100, so the work grows by ${100}^2={10}^4$. The time becomes $0.1\times {10}^4=1000$ seconds, about 17 minutes. A machine 100 times faster brings that to 10 seconds, which is a genuine improvement, but note what the same money buys on the input side: at fixed time budget, a machine 100 times faster handles only 10 times the input, since $\sqrt{100}=10$. Hardware buys you a square root; a better algorithm buys you a different exponent.

Now you. A cubic algorithm takes 1.0 second on $n=1000$. How long does it take on $n=5000$?

Combining bounds

Four rules cover almost every analysis you will do, and each follows from the definition in a line or two.

Sums take the maximum. If $f_1=O(g_1)$ and $f_2=O(g_2)$ then $f_1+f_2=O(\max (g_1,g_2))$. Two loops one after the other, one linear and one quadratic, cost $O(n^2)$ in total. This is why the dominant term is the only one written.

Products multiply. A loop running $n$ times whose body costs $O(n)$ costs $O(n^2)$. A loop running $n$ times whose body costs $O(\log n)$ costs $O(n\log n)$, which is the shape of "sort by inserting each element into a balanced tree".

Constants disappear. $O(3n)=O(n)$, and ${\log }_{b}n={\log }_{2}n/{\log }_{2}b$, so the base of a logarithm is a constant factor and vanishes: $O(\log n)$ needs no base. Note that this is not true in an exponent, where $2^n$ and $3^n$ differ by ${1.5}^n$, which is not a constant.

Nested loops are not automatically $n^2$. A loop where the inner bound depends on the outer index needs the sum evaluated. The nested duplicate check of the previous lesson runs its inner loop $n-1-i$ times, summing to $n(n-1)/2=\Theta (n^2)$, whereas a loop that halves a counter each pass runs $\Theta (\log n)$ times regardless of the outer loop.

Example. A function loops $i$ from 1 to $n$, and for each $i$ it loops $j$ from 1 to $i$, doing constant work in the body. Then it makes one pass over the array doing constant work. What is the total cost, tightly?

The double loop performs $\sum _{i=1}^{n}i=n(n+1)/2$ constant-cost iterations, which is $\Theta (n^2)$. The single pass is $\Theta (n)$. By the sum rule the total is $\Theta (\max (n^2,n))=\Theta (n^2)$, and the $\Theta$ is justified because the double loop is bounded both above and below by multiples of $n^2$: $n(n+1)/2\ge n^2/2$ and $\le n^2$.

Now you. A function loops $i$ from 1 to $n$, and for each $i$ it repeatedly halves a counter starting at $n$ until it reaches 1, doing constant work each halving. What is the cost?

Four ways this misleads

The notation is a tool for discarding information, and it is worth being explicit about what gets discarded, because every one of these has cost somebody a week.

Constants matter at real sizes. Suppose insertion sort costs $n^2/4$ steps and mergesort costs $8n{\log }_{2}n$, which are plausible ratios once the recursion, the allocation and the copying in mergesort are counted. Setting them equal gives $n=32{\log }_{2}n$, solved by $n=256$. Below 256 elements the "worse" algorithm wins, and at $n=50$ it wins by a factor of 3.6. This is not a curiosity: real sort implementations switch to insertion sort on small blocks for exactly this reason, and Timsort, the sort in Python and in Java's Arrays.sort for objects, chooses a minimum run length between 32 and 64 and insertion-sorts anything shorter.

$O$ is an upper bound, and people read it as tight. "Quicksort is $O(n^2)$" and "quicksort is $O(n\log n)$ on average" are both true statements about the same algorithm, and a reader who does not notice which bound is being quoted will draw the wrong conclusion. Worse is the common phrase "at least $O(n)$", which is meaningless: $O$ is already an upper bound, so "at least an upper bound" says nothing. The word wanted there is $\Omega$.

Asymptotic means eventually, and eventually can be absurd. Strassen's 1969 matrix multiplication algorithm costs $\Theta (n^{{\log }_{2}7})=\Theta (n^{2.807})$ against the naive $\Theta (n^3)$, and it does win on real hardware, with measured crossovers in tuned implementations somewhere from a few dozen to a few hundred. The descendants of Coppersmith and Winograd's method go much further, down to an exponent of about 2.372 in the current record, and none of them beats anything at any size a computer will ever be given, because their constants are astronomical. Such results are called galactic algorithms, and they are genuine mathematics with no engineering content.

Steps are not the only resource. The count says nothing about memory, and mergesort's extra array is the reason quicksort survives. It says nothing about cache behaviour, and a $\Theta (n)$ walk over a linked list scattered through memory can lose to a $\Theta (n\log n)$ pass over a contiguous array. It says nothing about the cost of the operations themselves, and every claim so far has quietly assumed that comparing two elements and reading a[i] cost the same fixed amount.

That last assumption is the one to attack next. Whether reading an element costs a constant depends entirely on how the elements are arranged in memory, and the two arrangements available, one block or a chain of separately allocated cells, give completely different cost tables for exactly the same operations. The next lesson starts with the block.

Every cost claim so far assumed that reading a[i] costs one step, and whether that is true depends entirely on how the elements are laid out in memory.

One block, and what an index really is

An array is a single contiguous block of memory holding $n$ elements of equal size $s$ bytes, starting at some base address $B$. That is the whole definition, and every property of arrays follows from it mechanically.

The element at index $i$ begins at address $B+is$. That is one multiplication and one addition, whatever $i$ is. Reading a[0] and reading a[999999] cost the same, because neither involves looking at anything in between. This is what random access means, and it is not a small thing: it is the property that makes binary search possible three lessons from now, and the property a linked list gives up in the next lesson.

The cost is the same, but the time need not be, and the difference is worth naming once. Under the RAM model both reads are one step. On real hardware a read whose target is already in the level-1 cache takes about a nanosecond, and one that goes out to main memory takes on the order of a hundred. Because caches load whole lines, typically 64 bytes, walking an array from front to back gets seven or eight elements free for every one that costs a trip to memory. Arrays are fast in practice for a reason the RAM model cannot see, and every structure in this course that scatters its elements pays a price the step count does not show.

Example. An array of 8-byte numbers begins at address 4096. At what address does element 250 begin, and how many memory cells were examined to work that out?

The address is $B+is=4096+250\times 8=6096$. No cells were examined. The address came from arithmetic on $i$ alone, which is precisely why the cost does not depend on $i$.

Now you. The same array is reindexed so that its first valid index is 1 rather than 0, with the block still starting at 4096 and element 1 stored first. Where does element 250 begin?

The price of contiguity

The same property that makes indexing free makes structural change expensive, and the two are the same fact seen from opposite sides. Contiguity says element $i$ is at $B+is$; that formula has to keep holding after the change, so the elements must physically move.

To insert a value at position $k$ in an array of $n$ elements, every element from $k$ to $n-1$ must move one slot to the right, which is $n-k$ moves. Inserting at the front costs $n$ moves; at the back it costs none. If insertion positions are uniformly distributed over the $n+1$ possible slots, the expected number of moves is about $n/2$. Deletion is the same in reverse: removing element $k$ shifts $n-k-1$ elements left.

So an array's cost table has two very different entries. Read or write by index: $\Theta (1)$. Insert or delete anywhere but the end: $\Theta (n)$.

There is one escape worth knowing, because it is used constantly and looks like cheating. If the order of the elements does not matter, deleting element $k$ can be done by moving the last element into slot $k$ and shrinking the length, which is $\Theta (1)$. Order is a requirement people assume without noticing they have assumed it, and dropping it here turns a linear operation into a constant one.

An array that grows

A block of memory has a fixed size, decided when it is allocated. Yet every language offers something that behaves like an array you can push onto forever: JavaScript's Array, C++'s std::vector, Java's ArrayList, Python's list. All of them are the same construction, called a dynamic array or growable array, and the construction is worth deriving because its analysis needs a genuinely new idea.

The structure holds three things: a block, its capacity (how many elements the block can hold) and its length (how many it currently holds), with length never exceeding capacity. Pushing writes to slot length and increments the length, which is $\Theta (1)$, until length equals capacity. At that point the push cannot proceed, so the structure allocates a bigger block, copies every existing element across, frees the old block, and then does the write.

That copy is $\Theta (n)$. So a single push has worst-case cost $\Theta (n)$, and if you stop the analysis there you conclude that dynamic arrays are terrible, which contradicts the fact that everyone uses them. The worst case is a true statement about one operation and a misleading statement about a sequence of them, because an expensive push guarantees that the next many pushes are cheap.

Amortised cost

Amortised analysis asks a different question: not what the worst single operation costs, but what the worst sequence of $m$ operations costs, divided by $m$. It is a worst-case statement, not an average-case one. There is no probability in it and no assumption about which inputs occur. It says: however you choose the operations, the total is bounded.

Take the growth rule "when full, allocate a block of double the capacity". Start from capacity 1 and push $n$ elements. Reallocation happens when the length reaches 1, 2, 4, 8, and so on, and the copy at each of those points moves the current contents: 1 element, then 2, then 4, and so on. The total number of elements copied over the whole sequence is

where $2^k$ is the final capacity. Concretely, growing to a million elements from capacity 1 does 20 reallocations and copies 1,048,575 elements in total, roughly one copy per element pushed.

Add the $n$ writes of the pushed values themselves and the total for $n$ pushes is under $3n$ operations, so the amortised cost of a push is $O(1)$: about two operations each, a write and a copy. No individual push is guaranteed cheap. The sequence is.

Now try the other obvious growth rule: when full, allocate a block with a fixed number of extra slots, say 1000 more. Reallocation now happens every 1000 pushes, and the copies are 1000, then 2000, then 3000, and so on. Reaching a million elements takes 999 reallocations and copies

elements: 476 times more copying than doubling, for the same result. In general, growing by a fixed $c$ costs $\Theta (n^2/c)$ total, so the amortised cost per push is $\Theta (n/c)$, which is linear, not constant. The constant $c$ postpones the problem and does not remove it. This is the whole argument for multiplicative growth, and it is why every library implementation uses a growth factor rather than a growth increment.

Example. A dynamic array with growth factor 2 starts at capacity 1 and receives 1000 pushes. How many reallocations occur, and how many element copies in total?

Capacities go 1, 2, 4, ..., 1024, so reallocations happen at lengths 1, 2, 4, ..., 512: ten of them. The copies total $1+2+4+\cdots +512=1023$ elements. Against 1000 pushes that is 1.02 copies per push, and adding the pushes themselves gives about 2.0 operations per push, exactly as the amortised bound predicts.

Now you. The same array instead grows by 100 slots each time it fills, starting from capacity 100. How many copies in total to reach 1000 elements, and how does that compare?

Which factor, and what it costs in memory

Doubling is not the only multiplicative rule, and the choice is a real engineering trade rather than a detail.

With growth factor $g$, the capacities form a geometric sequence and the total copies to reach $n$ elements are about $n/(g-1)$. So $g=2$ copies each element about once, $g=1.5$ copies it about twice, and $g=4$ about a third of a time. Larger $g$ means less copying.

The price is memory. Immediately after a growth the block is $g$ times larger than the data in it, so up to $(g-1)/g$ of the allocation is empty: half the block wasted at $g=2$, three quarters at $g=4$. For an array of a hundred million records that is not a rounding error.

There is a subtler argument for $g=1.5$, and it is a nice example of a real constraint that no asymptotic analysis can see. Consider whether the memory freed by earlier reallocations can be reused for the next block. Under doubling, the total freed so far when asking for a block of size $2^k$ is $1+2+\cdots +2^{k-1}=2^k-1$, which is always just short of what is needed, forever. Under any factor below the golden ratio $\phi =1.618$, the freed blocks eventually add up to more than the next request, so an allocator can reuse them. Facebook's folly::fbvector uses 1.5 for exactly this reason, while std::vector in the GNU and LLVM standard libraries uses 2, and Python's list grows by roughly 1.125 with a small constant added, since it also cares about small lists.

Note also what shrinking must not do. If a dynamic array halves its block as soon as the length falls below half the capacity, then repeatedly pushing and popping across the boundary makes every operation reallocate, and the amortised bound collapses to $\Theta (n)$ per operation. The standard fix is hysteresis: shrink only when the length falls below a quarter of the capacity, which leaves room for the length to move without triggering another reallocation.

Example. A dynamic array uses growth factor 1.5. Roughly how many element copies does building it up to $n={10}^6$ elements cost, and how much memory can be wasted at worst?

Total copies are about $n/(g-1)={10}^6/0.5=2\times {10}^6$, so about two copies per element, twice the doubling scheme's one. The wasted fraction just after a growth is $(g-1)/g=0.5/1.5=1/3$, so at worst about a third of the block is empty, against a half under doubling.

Now you. A dynamic array uses growth factor 4. How many copies per element does it make, and what fraction of the block can be empty?

What amortised does and does not promise

Amortised constant is a strong guarantee about totals and no guarantee at all about any individual operation, and the difference matters in exactly one setting, which is worth stating plainly rather than leaving as a footnote.

If a program is rendering a frame every 16 milliseconds, or holding a lock, or steering something, then a single push that stops to copy ten million elements is a failure even though the average is fine. Systems with that requirement use structures with worst-case constant bounds, which exist and are built by copying incrementally: on each push, move a few elements from the old block to the new one, so that the migration finishes before the new block fills. The total work is the same and the peak is bounded, at the cost of holding two blocks at once and of more complicated code.

For everything else, amortised constant is the right guarantee and dynamic arrays are the right default. The remaining problem is the one this lesson could not fix. Growing is solved, but inserting or deleting anywhere except the end is still $\Theta (n)$, and no growth policy touches that, because it is forced by contiguity itself. The elements are neighbours in memory, so making room for one means moving the rest.

The only way out is to stop requiring them to be neighbours. If each element carries the address of the next one, the elements can sit anywhere, and inserting between two of them is a matter of rewriting two addresses. That buys constant-time insertion and, as the next lesson shows, immediately loses the constant-time indexing this one opened with.

Inserting into the middle of an array is linear because the elements are neighbours in memory, and the only way out is to stop requiring that they are.

A node that names its successor

The alternative to one block is many small blocks, each holding one element together with the address of the next. Such a block is a node, the address it holds is a pointer or reference, and a chain of them is a singly linked list. The list itself is nothing but a pointer to the first node, called the head; the last node's pointer is null, which is how the end is recognised.

The nodes may sit anywhere in memory, in any order. Nothing about their addresses encodes their position in the sequence, and that single fact generates the entire cost table.

Consider inserting a new value between two existing nodes. You allocate a node, point it at the second node, and rewrite the first node's pointer to point at the new one. Two pointer writes, one allocation, done, regardless of how long the list is or where in it you are. The array had to move $n-k$ elements to achieve the same thing; the list moves nothing, because nothing is where it is for a reason.

Deletion of the node after a known node is the same idea: copy the doomed node's pointer into its predecessor and release it. Again constant, again independent of length.

That is the purchase. Now the price.

What contiguity was paying for

To reach the element at position $i$, there is no arithmetic to do, because the address of node $i$ is not a function of $i$. It is stored inside node $i-1$, whose address is stored inside node $i-2$, and so on. The only way to find it is to start at the head and follow $i$ pointers. Indexing is $\Theta (n)$ where the array's was $\Theta (1)$.

This poisons more than it first appears to. The constant-time insertion above assumed you already held a pointer to the node you were inserting after. If you know only the position, you must walk to it first, and the walk is linear, so "insert at position $k$" costs $\Theta (k)$ in a linked list and $\Theta (n-k)$ in an array. Neither is better in general; they are expensive in opposite places.

The honest statement is therefore narrow: a linked list gives constant-time insertion and deletion at a position you already hold a reference to. That is exactly the situation in an LRU cache, where a hash table hands you the node directly, or in an iterator that is already standing where it needs to edit. It is not the situation in most code, which is why the array wins more often than the textbook cost table suggests.

Example. A structure holds 10,000 elements and you want to insert a value at position 5000, knowing only the position. Count the elementary operations for an array and for a singly linked list.

The array shifts every element from index 5000 to 9999 one slot right: $10000-5000=5000$ moves, then one write. The list follows 4999 pointers to reach node 4999, then does two pointer writes: about 5001 operations. The counts are within a fraction of a per cent of each other, both $\Theta (n)$, and the array's operations are sequential memory writes while the list's are scattered reads, so the array is faster in practice by a wide margin.

Now you. The same two structures, but now you want to insert at position 100. Count the operations for each.

Doubly linked, and what the second pointer buys

A singly linked list cannot delete a node it is standing on, because deletion requires rewriting the predecessor's pointer and the predecessor is unreachable. It also cannot be walked backwards. Both are fixed by giving each node a second pointer, to its predecessor, producing a doubly linked list.

Now deleting a node you hold is genuinely constant: read its two neighbours from its own fields, point them at each other, release it. Insertion before a known node becomes possible too. Most library list types, including std::list and Java's LinkedList, are doubly linked for these reasons, usually with a sentinel node joining the two ends into a ring so that the empty case and the end cases need no special code.

The cost is memory and bookkeeping. Suppose the payload is an 8-byte number on a 64-bit machine. An array of a million such values occupies 8 MB, exactly the data. A singly linked list needs 8 bytes of payload plus an 8-byte pointer per node, so 16 MB, double. A doubly linked list needs 24 MB, triple. And that is before the allocator: a general-purpose malloc typically adds a header of about 16 bytes to each separate allocation and rounds sizes up, so a real singly linked list of a million small nodes can occupy 32 MB or more, four times the data it holds.

The performance consequence is larger than the memory one. A cache line is typically 64 bytes, so an array of 8-byte elements delivers eight elements per trip to memory: a full scan of a million elements causes about 125,000 memory fetches. The nodes of a linked list, allocated at different times, are scattered, so each hop is likely to be its own fetch: about a million of them. At roughly 100 nanoseconds for a fetch that misses cache, the scan costs about 12 milliseconds against 100 milliseconds, a factor of eight that the step count says nothing about, both being $\Theta (n)$.

Stacks: last in, first out

The interesting move now is not to add capability but to remove it. A stack supports exactly three operations: push a value on the top, pop the top value off, and look at the top without removing it. All three are constant time, and the discipline that results is last in, first out.

Both layouts implement it well. On a dynamic array, push and pop act at the end, which is the cheap end, giving amortised constant cost with excellent cache behaviour. On a linked list, push and pop act at the head, which is the node you already hold, giving true worst-case constant cost with no reallocation ever.

The reason a restricted interface is worth having is that many problems are exactly stack-shaped, and saying so is a design decision rather than an implementation detail. Matching brackets in an expression is: push each opener, and on each closer check that the popped opener matches. Undo histories are. Depth-first search, in the graph lessons, is. And the call stack that made recursion possible in the previous course is literally one: each call pushes a frame holding the parameters and the return address, each return pops one, and a runaway recursion overflows it, which is what a stack overflow is.

Queues, and the ring buffer

A queue reverses the discipline: enqueue at the back, dequeue from the front, first in first out. It is the right structure whenever fairness or arrival order matters, which is most of scheduling, most of message passing, and the traversal in the graph lessons that finds shortest paths by edge count.

Implementing it on a linked list is immediate: keep pointers to both head and tail, enqueue at the tail, dequeue from the head, both constant.

Implementing it on an array takes one idea. Dequeuing from index 0 and shifting everything left is $\Theta (n)$ and unacceptable, so instead the queue keeps two indices, a head and a size, and lets the contents wrap around the end of the block. Element $i$ of the queue lives at slot $(\text{head}+i)\text{mod}\text{capacity}$. Enqueue writes at $(\text{head}+\text{size})\text{mod}\text{capacity}$ and increments the size; dequeue returns slot head, advances head modulo the capacity, and decrements the size. That is a ring buffer or circular buffer, both operations constant, no shifting, no allocation, and it is what sits behind most audio pipelines, network buffers and lock-free producer-consumer channels.

A deque, or double-ended queue, allows insertion and removal at both ends, and is what you get by allowing head to move backwards too. Python's collections.deque is a linked list of fixed-size blocks; C++'s std::deque is an array of pointers to fixed-size blocks. Both are attempts to get the ring buffer's locality without its fixed capacity.

Example. A ring buffer has capacity 8, its head is at slot 6, and it currently holds 5 elements. Which slot holds queue element 3, and which slot will the next enqueue write to?

Element $i$ is at $(6+i)\text{mod}8$, so element 3 is at $(6+3)\text{mod}8=1$. The next enqueue writes at $(6+5)\text{mod}8=3$. The occupied slots are 6, 7, 0, 1, 2, which is the wrap that gives the structure its name.

Now you. From that state, two elements are dequeued and three are enqueued. Where is the head now, how many elements are held, and which slot holds element 0?

Choosing between them

The cost table is the smaller half of the decision, and it is worth writing out honestly, with $n$ the number of elements.

The last two rows are why the recommendation from practice is blunter than the table above them: prefer the dynamic array unless you have a specific reason not to. The reasons that count are holding stable references to elements that must survive insertions elsewhere, splicing whole sublists in constant time, needing a hard worst-case bound with no reallocation pause, and hardware without enough contiguous memory to hold a large block.

Example. A program keeps a list of a million records and its dominant operation is walking the whole list to sum a field, done thousands of times. Occasionally a record is inserted in the middle. Which structure?

The dynamic array. The dominant operation is a scan, where the array wins by about a factor of eight on memory traffic; the rare insertion costs $\Theta (n)$, about half a million moves of contiguous memory, which is a few hundred microseconds and happens rarely. Optimising the rare operation at the cost of the frequent one is the standard way to make a program slower while believing you improved it.

Now you. A cache holds a million entries and must, on every access, move the accessed entry to the front of a recency order, given a pointer to it from a hash table. Which structure, and why?

Both layouts share one weakness, and it is total. To find an element whose position you do not know, there is nothing to do but look at them all: $\Theta (n)$, for an array and for a list alike, no matter how the memory is arranged. The next lesson removes that cost, at the price of a precondition that nothing so far can supply.

Finding an element whose position you do not know costs a look at every element, in an array and in a linked list alike, and the only way to escape that is to know something about the order the elements are in.

What order buys

Take an array of $n$ elements held in ascending order, and compare the target $x$ with the element in the middle. Three outcomes are possible. If they are equal, the search is over. If $x$ is smaller, then because the array is sorted, $x$ cannot be anywhere in the upper half: every element there is at least as large as the middle one. If $x$ is larger, it cannot be in the lower half.

A single comparison has eliminated half the array. Nothing about the layout of memory made that possible; the ordering did. And crucially, examining the middle element is only cheap because the structure is an array, where the middle is one multiplication away. A sorted linked list gains nothing from being sorted, because reaching its middle costs $n/2$ hops, which is the whole saving.

Both preconditions are essential and both are easy to violate silently. Binary search on unsorted data does not report an error; it returns a wrong answer, quickly.

The invariant

The algorithm keeps two indices, lo and hi, delimiting the part of the array still under consideration, and maintains one property throughout:

If $x$ is present in the array at all, its index lies in $[\text{lo},\text{hi}]$.

Initially $\text{lo}=0$ and $\text{hi}=n-1$, and the invariant holds trivially. Each round computes $\text{mid}$ between them and compares. If $a[\text{mid}]=x$, return. If $a[\text{mid}]<x$, then no index at or below mid can hold $x$, so setting $\text{lo}=\text{mid}+1$ preserves the invariant. If $a[\text{mid}]>x$, setting $\text{hi}=\text{mid}-1$ preserves it. When $\text{lo}>\text{hi}$ the interval is empty, and the invariant then says $x$ is not present, which is the correct return.

Termination is separate from correctness and needs its own argument. The interval width $\text{hi}-\text{lo}+1$ strictly decreases on every round, because mid lies within the interval and each branch excludes mid itself. A strictly decreasing non-negative integer cannot decrease forever, so the loop ends. Any implementation that lets the width stay the same on some round loops forever, and that is not hypothetical: it is the second of the two classic bugs below.

Example. Trace a binary search for 41 in the array 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, which has 15 elements at indices 0 to 14.

Round 1: $\text{lo}=0$, $\text{hi}=14$, $\text{mid}=7$, $a[7]=19<41$, so $\text{lo}=8$. Round 2: $\text{lo}=8$, $\text{hi}=14$, $\text{mid}=11$, $a[11]=37<41$, so $\text{lo}=12$. Round 3: $\text{lo}=12$, $\text{hi}=14$, $\text{mid}=13$, $a[13]=43>41$, so $\text{hi}=12$. Round 4: $\text{lo}=12$, $\text{hi}=12$, $\text{mid}=12$, $a[12]=41$, found.

Four comparisons, against an expected eight for a linear scan of a 15-element array.

Now you. Trace the same search for 13 in the same array. How many comparisons?

Counting it exactly

Each round at worst halves the interval, so after $k$ rounds the interval holds at most $n/2^k$ elements. The search finishes when that falls below one, which happens at $k=\lfloor {\log }_{2}n\rfloor +1$, equivalently $\lceil {\log }_2(n+1)\rceil$. The two expressions agree for every positive $n$, and either is the exact worst-case number of comparisons.

The numbers are what make the point.

Twenty comparisons to search a million items; thirty for a billion. Each doubling of the data adds exactly one comparison, which is what logarithmic cost means in practice and why it is treated as effectively free. A linear scan of the same billion items averages 500 million comparisons.

Note that the sorted array is not free. Keeping it sorted under insertions costs $\Theta (n)$ per insertion, because a new element has to be placed in order and everything after it shifted. Binary search is therefore the right structure for data that is read far more often than written: a lookup table, a static index, a sorted array of identifiers rebuilt in a batch.

Example. You have a million records and need to perform $k$ lookups. Linear search averages $n/2$ comparisons each. Sorting first costs about $n{\log }_{2}n$ comparisons, after which each lookup costs 20. Above what $k$ is sorting worth it?

Linear costs $500\{,\}000k$. Sorting plus searching costs ${10}^6\times 19.93+20k=1.993\times {10}^7+20k$. Setting them equal: $499\{,\}980k=1.993\times {10}^7$, so $k\approx 40$. Above about forty lookups, sorting pays for itself; below it, scanning is cheaper. The answer is far smaller than most people guess, which is the practical lesson.

Now you. Same numbers, but the data changes constantly, so the array must be re-sorted after every lookup. Now which wins?

Nobody can do better, and here is why

Twenty comparisons for a million elements is impressive, but impressive is not a proof. The stronger claim is that no algorithm restricted to comparing the target against elements can do better, and it can be proved with an argument that recurs several times later in this course.

Model any such algorithm as a decision tree. Each internal node is a comparison the algorithm might make, each edge is an outcome, and each leaf is an answer the algorithm can produce. Running the algorithm on a particular input traces one root-to-leaf path, and the number of comparisons made is that path's length. The worst-case comparison count is therefore the height of the tree.

Now count the leaves that must exist. The algorithm has to be able to answer "the target is at index 0", "at index 1", up to "at index $n-1$", and "not present": at least $n+1$ distinct answers. Distinct answers need distinct leaves, since the algorithm has learned nothing to separate them otherwise.

A binary tree of height $h$ has at most $2^h$ leaves. So $2^h\ge n+1$, giving

and since $h$ is an integer, $h\ge \lceil {\log }_2(n+1)\rceil$. That is exactly what binary search achieves, so binary search is optimal, not merely good.

Be precise about what has been ruled out. The bound applies to algorithms whose only access to the data is comparing elements. It does not forbid an algorithm that looks at the value of the key and computes where it should be. Interpolation search does exactly that, guessing the position by linear interpolation between the endpoints, and on uniformly distributed data it costs about ${\log }_2{\log }_{2}n$ comparisons: roughly 4.3 for a million items instead of 20. Its worst case, on badly skewed data such as exponentially spaced keys, degrades to $\Theta (n)$, which is why it is rarely the default. The same loophole, exploited harder, is what makes hash tables constant time, and it is the subject of a later lesson.

The two bugs everyone writes

Binary search is six lines long and notoriously difficult to write correctly. Jon Bentley reported that when he set it as an exercise to professional programmers, about ninety per cent of the submissions were wrong, and Knuth notes that although the method was published in 1946, the first correct published version of the general case did not appear until 1962.

The overflow. The natural way to compute the midpoint is $\text{mid}=(\text{lo}+\text{hi})/2$. If indices are 32-bit signed integers and the array is large, the sum overflows before the division. With $\text{lo}$ and $\text{hi}$ near $2^{31}-1=2\{,\}147\{,\}483\{,\}647$, their sum is about $4.29\times {10}^9$, which wraps to a negative number, and the subsequent index is out of bounds. This is not a textbook worry: it sat in the JDK's Arrays.binarySearch from version 1.2 until Joshua Bloch found and reported it in 2006, nine years, in code that had been read by thousands of people. The fix is to compute $\text{mid}=\text{lo}+(\text{hi}-\text{lo})/2$, which is algebraically identical and never forms the large sum.

The non-shrinking interval. Write the loop as while (lo < hi) with the update $\text{hi}=\text{mid}$ rather than $\text{mid}-1$, which is the shape used for finding a boundary rather than an exact match. When $\text{hi}=\text{lo}+1$, the floor division gives $\text{mid}=\text{lo}$, and if the branch taken sets $\text{lo}=\text{mid}$, the interval does not shrink and the loop runs forever. The rule that prevents it is the termination argument above: check that every branch strictly reduces $\text{hi}-\text{lo}$. Where the update is $\text{lo}=\text{mid}$, the midpoint must round up instead, $\text{mid}=\text{lo}+\lceil (\text{hi}-\text{lo})/2\rceil$.

Searching for a boundary

Exact-match search is the least useful of the binary search family, and the variants matter more in practice. The two standard ones answer "where does $x$ belong?" rather than "is $x$ here?".

Lower bound returns the index of the first element not less than $x$: the position of $x$'s first occurrence if it is present, and the insertion point if it is not. Upper bound returns the index of the first element strictly greater than $x$. The difference between them is the number of copies of $x$ in the array, computed in $2\lceil {\log }_2(n+1)\rceil$ comparisons without examining the duplicates at all.

These are what libraries actually expose: std::lower_bound and std::upper_bound in C++, bisect_left and bisect_right in Python. They answer range queries ("how many values lie between 100 and 200?") and they never need a separate "not found" convention, since a position is always meaningful. They are also the reason binary search generalises past arrays: any monotone predicate over an ordered domain can be bisected, which is how you find the smallest capacity that satisfies a constraint, or the first commit that broke a build. That last one is git bisect, and it finds the culprit among a thousand commits in ten builds.

Example. In the array 2, 4, 4, 4, 7, 9, what do lower bound and upper bound return for $x=4$, and what does the pair tell you?

Lower bound returns 1, the first index whose element is not less than 4. Upper bound returns 4, the first index whose element exceeds 4. The difference $4-1=3$ is the number of 4s in the array.

Now you. In the same array, what do lower bound and upper bound return for $x=5$, and what does that say?

Every result in this lesson rests on a precondition that nothing in the course can yet supply: the array must already be in order. Producing that order is a problem in its own right, and the obvious methods for it turn out to cost quadratically, which is the subject of the next lesson.

Binary search needs its array in order, and nothing so far puts it there, so this lesson builds the three obvious methods and measures exactly how far they get.

Selection sort: the fewest possible moves

The first idea most people have is also the most direct. Find the smallest element and put it first. Find the smallest of what remains and put it second. Repeat.

Concretely, for $i$ from 0 to $n-2$, scan the range from $i$ to $n-1$ for the minimum and swap it into position $i$. After round $i$ the first $i+1$ positions hold the $i+1$ smallest elements in order, which is the invariant, and after $n-1$ rounds the array is sorted.

The comparison count is exact and unconditional. Round $i$ compares the current minimum against $n-1-i$ candidates, so the total is

the same sum as the duplicate check two lessons ago: 499,500 comparisons for a thousand elements. Selection sort does exactly that many on every input of size $n$. Already-sorted input, reverse-sorted input, random input: identical work. Best case equals worst case equals average case, which is unusual and not a virtue, since it means the algorithm cannot notice that its job is already done.

What it does minimise is data movement. At most one swap per round, so at most $n-1$ swaps, $\Theta (n)$ rather than $\Theta (n^2)$. That is the one situation where selection sort is the right answer: when comparisons are cheap and moving an element is very expensive, as when sorting large records in place rather than sorting an array of pointers to them.

Insertion sort, and what it is really counting

The second idea is how people sort a hand of cards. Take the elements one at a time and insert each into its place among the ones already sorted, shifting the larger ones right to make room.

For $i$ from 1 to $n-1$, hold $a[i]$ aside as the key, then walk backwards from $i-1$ shifting every element greater than the key one slot right, and drop the key into the gap. The invariant is that $a[\mathrm{0..}i-1]$ is sorted at the start of round $i$, which it is at $i=1$ because a single element is sorted.

Unlike selection sort, the work depends heavily on the input. On already-sorted input each key is compared once with its predecessor, fails the test immediately, and stays put: $n-1$ comparisons, zero moves, $\Theta (n)$ total. On reverse-sorted input every key travels the whole way to the front: $n(n-1)/2$ comparisons and as many moves. Between those extremes the cost is governed by one quantity, and naming it is the point of this section.

An inversion of an array is a pair of positions $i<j$ with $a[i]>a[j]$: a pair that is in the wrong relative order. A sorted array has zero inversions. A reverse-sorted array has $n(n-1)/2$, the maximum, since every pair is wrong. And a random permutation has, on average, exactly half the maximum, $n(n-1)/4$, because for each of the $n(n-1)/2$ pairs the two orders are equally likely.

Here is the connection. Each move insertion sort makes shifts one element past the key, and that shift removes exactly one inversion, since the pair was out of order before and in order after. No move removes more than one and none removes fewer, so

exactly, where $I$ is the number of inversions in the input. The comparisons are the moves plus at most one extra per round, so they are at most $I+n-1$.

That is a much sharper statement than "insertion sort is $\Theta (n^2)$". It says the cost is linear in the disorder, so an array that is nearly sorted, meaning $I=O(n)$, is sorted in linear time. It also explains why the average is quadratic: a random array has $n(n-1)/4$ inversions, about 250,000 for a thousand elements, so the average cost is half the worst case rather than a different shape.

Example. Run insertion sort on 5, 2, 4, 6, 1, 3. How many inversions does the input have, and how many moves and comparisons does the sort make?

The inverted pairs are (5,2), (5,4), (5,1), (5,3), (2,1), (4,1), (4,3), (6,1), (6,3): nine of them. Insertion sort makes exactly nine moves, as predicted. The comparisons number 12: the nine that caused a move, plus one wasted comparison at the end of each of the three rounds whose key did not travel all the way to the front.

Now you. How many inversions are in 2, 3, 5, 7, 11, 4, and how many moves will insertion sort make?

Bubble sort, and why it is the worst of the three

The third idea is to repeatedly sweep the array, swapping any adjacent pair that is out of order, until a whole sweep makes no swap. After the first sweep the largest element has been carried to the end, after the second the next largest, and so on, which is where the name comes from.

Bubble sort makes the same $n(n-1)/2$ comparisons in the worst case, and its swaps also equal the inversion count, since each adjacent swap fixes exactly one inversion. With the early-exit check it is $\Theta (n)$ on already-sorted input, so it is adaptive too. On every other input it loses to insertion sort, because it performs a full swap, three assignments, where insertion sort performs one shift, and it re-examines pairs that insertion sort has already settled.

It is worth being direct about this, because bubble sort is taught more than any other sort and used less than any. Knuth's verdict in The Art of Computer Programming is that it has nothing to recommend it except its catchy name and the fact that it leads to some interesting theoretical problems. There is no input and no machine on which bubble sort is the best of the three. Learn it to recognise it, and reach for insertion sort.

Stability, and why it is not a detail

A sort is stable if elements that compare equal keep their original relative order. Selection sort as described is not stable, because the long-range swap can jump one element over an equal one. Insertion sort is stable, provided the shifting test is strictly "greater than" rather than "greater or equal", since then an incoming key stops as soon as it meets an equal element and settles after it. Bubble sort is stable for the same reason.

Stability sounds like pedantry until you need to sort by two keys. Suppose a table of employees is to be ordered by department, and within each department by surname. With a stable sort the job is two passes: sort by surname, then sort by department. The second sort moves whole departments into place and, being stable, leaves the surname order inside each department untouched. With an unstable sort that trick does not work at all and you must write a comparison function that compares both fields, which is more code and, more importantly, has to be changed every time the user picks a different column to sort by. This is exactly why spreadsheet and table-view sorting is specified as stable.

The cost of stability is real: the fastest in-place sorts, quicksort and heapsort, are both unstable, and the standard stable sort, mergesort, needs extra memory. Language libraries split on the question. Java's Arrays.sort on objects is Timsort and stable, while on primitives it is a dual-pivot quicksort and unstable, on the grounds that two equal integers are indistinguishable so nobody can tell. C++ offers std::sort (unstable, fast) and std::stable_sort separately, which is the honest interface.

Example. A list holds (Ada, Engineering), (Bo, Sales), (Cy, Engineering), (Di, Sales) in that order. It is sorted by name, then by department, with a stable sort. What comes out?

Sorting by name gives Ada, Bo, Cy, Di. Sorting that by department moves both Engineering rows ahead of both Sales rows, and stability preserves the name order within each group, giving (Ada, Engineering), (Cy, Engineering), (Bo, Sales), (Di, Sales). Names ascend inside each department without any comparison function ever mentioning names and departments together.

Now you. The same list, sorted first by department and then by name, with a stable sort. What comes out, and what does that tell you about the order of the passes?

The wall, in seconds

The three algorithms differ in constants and in adaptivity, and not at all in shape: all are $\Theta (n^2)$ in the average and worst cases. It is worth seeing what that costs, on a machine doing ${10}^9$ comparisons a second.

At a thousand elements the difference is invisible and the simpler code wins. At a million it is eight minutes against a fiftieth of a second, and at ten million the quadratic sort has left the range of things anyone waits for. The wall arrives somewhere in the tens of thousands, and it arrives suddenly, which is the usual way a program that worked in testing fails in production.

Example. An insertion sort takes 5.0 seconds on 100,000 random records. A colleague suggests running it on 400,000. How long, and what would a machine four times faster achieve?

Cost scales as $n^2$ on random input, and $n$ grew by a factor of 4, so the work grows by 16: about 80 seconds. A machine four times faster brings that back to 20 seconds, still four times the original. The alternative is to change the shape: an $n{\log }_{2}n$ sort on 400,000 elements is about $7.4\times {10}^6$ comparisons, roughly 7 milliseconds, which is four orders of magnitude better than anything the hardware could buy.

Now you. The same insertion sort is instead given 400,000 records that are already nearly sorted, with about 300,000 inversions in total. Roughly how long?

Why quadratic is unavoidable here

Every one of these three algorithms shares a structural feature: they compare and move adjacent or nearly adjacent elements. Insertion sort and bubble sort remove exactly one inversion per move, and a random array has $\Theta (n^2)$ inversions, so any algorithm that removes inversions one at a time is stuck at $\Theta (n^2)$ no matter how cleverly it is coded. This is not a limitation of the implementations; it is a limitation of the strategy.

Escaping it therefore requires moves that fix many inversions at once, which means comparing elements that are far apart. Selection sort's long-range swap does move elements far, but it learns nothing from the comparisons it makes along the way: each round rediscovers order it already had evidence for, throwing away $n$ comparisons to place a single element.

So the requirement for something better is an algorithm that both moves elements over long distances and keeps what its comparisons told it. The next lesson supplies a general strategy that does both by attacking the array's size directly, splitting the problem rather than the array's disorder, and it produces the first sort with a guaranteed $\Theta (n\log n)$ bound.

Every quadratic sort is stuck because it removes disorder one inversion at a time, so beating it needs an algorithm with a different shape entirely.

The shape

Divide and conquer is a three-step pattern. Divide the problem into smaller instances of the same problem. Conquer them by solving each recursively, stopping at a base case small enough to solve outright. Combine the sub-answers into an answer for the whole.

Binary search is already an instance, in a degenerate way: it divides into two halves, conquers one of them, and needs no combination step at all. What makes the pattern powerful is the case where both halves are solved and the combination is cheap, because then the work at each level of recursion is proportional to the data at that level, and the number of levels is logarithmic.

The reason this can beat $\Theta (n^2)$ is precisely the thing insertion sort could not do. When two sorted halves are merged, a single comparison between the fronts of the two halves can settle the relative order of one element against every remaining element of the other half at once. Each comparison carries more information than a comparison of neighbours, because the sortedness of the halves is being used.

Recurrences

A divide-and-conquer algorithm's cost is naturally written as an equation in terms of itself. If splitting into $a$ subproblems of size $n/b$ costs $f(n)$ for the dividing and combining, the total is

with a base case such as $T(1)=\Theta (1)$. This is a recurrence, and solving it means finding a closed form for $T(n)$.

The first method is the recursion tree, and it is the one to reach for because it shows why the answer is what it is. Draw the root as the top-level call, costing $f(n)$. It has $a$ children each costing $f(n/b)$, each of which has $a$ children costing $f(n/b^2)$, and so on until the subproblem size reaches 1, which happens at depth ${\log }_{b}n$. Sum the cost of each level, then sum the levels.

Take mergesort's recurrence, $T(n)=2T(n/2)+n$. The root costs $n$. Level 1 has two nodes costing $n/2$ each, total $n$. Level 2 has four nodes costing $n/4$ each, total $n$. Every level costs exactly $n$, and there are ${\log }_{2}n+1$ of them, so

The shape of the answer is visible in the drawing: the work per level is constant, so the total is work-per-level times number-of-levels.

Three other shapes occur. If the per-level total shrinks geometrically going down, as in $T(n)=2T(n/2)+n^2$, where levels cost $n^2$, $n^2/2$, $n^2/4$, the sum is dominated by the root and $T(n)=\Theta (n^2)$. If it grows geometrically, as in $T(n)=4T(n/2)+n$, where levels cost $n$, $2n$, $4n$, the sum is dominated by the leaves. If it stays level, as in mergesort, the logarithm appears.

Example. Solve $T(n)=2T(n/2)+\Theta (1)$ by recursion tree, and say which algorithm it describes.

Level 0 costs 1, level 1 costs 2, level 2 costs 4, and level $k$ costs $2^k$. At depth ${\log }_{2}n$ there are $n$ leaves, and the sum $1+2+4+\cdots +n=2n-1$ is dominated by the last level. So $T(n)=\Theta (n)$. This describes an algorithm that splits in two, recurses on both halves, and does constant work to combine: for instance finding the maximum of an array by halving, which does $n-1$ comparisons in total, the same as the obvious loop.

Now you. Solve $T(n)=T(n/2)+\Theta (1)$, and name the algorithm.

The master theorem

The recursion tree generalises into a formula, and the formula is worth having because most recurrences that arise in practice are of exactly this form. For $T(n)=aT(n/b)+f(n)$ with $a\ge 1$ and $b>1$, compare $f(n)$ against the quantity $n^{{\log }_{b}a}$, which is the total cost of the leaves.

If $f(n)=O(n^{{\log }_{b}a-\epsilon })$ for some $\epsilon >0$, the leaves dominate and $T(n)=\Theta (n^{{\log }_{b}a})$.

If $f(n)=\Theta (n^{{\log }_{b}a})$, every level costs about the same and $T(n)=\Theta (n^{{\log }_{b}a}\log n)$.

If $f(n)=\Omega (n^{{\log }_{b}a+\epsilon })$ for some $\epsilon >0$, and additionally $af(n/b)\le cf(n)$ for some $c<1$ and all large $n$, the root dominates and $T(n)=\Theta (f(n))$.

Applied: mergesort has $a=2$, $b=2$, so $n^{{\log }_{2}2}=n$, and $f(n)=n$ matches, giving case two and $\Theta (n\log n)$. Binary search has $a=1$, $b=2$, so $n^{{\log }_{2}1}=n^0=1$, and $f(n)=1$ matches, giving $\Theta (\log n)$. The obvious matrix multiplication algorithm splits each matrix into four blocks and does eight block multiplications plus $\Theta (n^2)$ additions: $a=8$, $b=2$, $n^{{\log }_{2}8}=n^3$ dominates $n^2$, so case one gives $\Theta (n^3)$, agreeing with the triple loop. Strassen's trick does seven block multiplications instead of eight, so $n^{{\log }_{2}7}=n^{2.807}$, which is where that exponent comes from.

The theorem has gaps, and pretending otherwise causes errors. It says nothing when $f(n)$ falls between two cases: $T(n)=2T(n/2)+n\log n$ has $n^{{\log }_{b}a}=n$, and $n\log n$ is bigger than $n$ but not by a factor of $n^{\epsilon }$, so no case applies. (A recursion tree settles it: $\Theta (n{\log }^{2}n)$.) It also assumes all subproblems have the same size, which quicksort's do not, so the next lesson needs a different method entirely.

Mergesort

Now build the sort. To sort $n$ elements: if $n\le 1$ it is already sorted; otherwise split the array in half, sort each half recursively, and merge the two sorted halves into one sorted whole.

The merge is the only part with content. Keep an index into each sorted half. Compare the two elements they point at, copy the smaller into the output, and advance that index. When one half is exhausted, copy the rest of the other. Every comparison consumes one element, so merging two runs of total length $m$ costs at most $m-1$ comparisons and exactly $m$ moves.

Correctness of the merge is the loop invariant that the output holds, in sorted order, exactly the elements already consumed from both inputs, and that every unconsumed element is at least as large as every consumed one. That second clause is what the sortedness of the halves buys, and it is why the smaller of the two front elements is safe to emit.

The cost recurrence is $T(n)=2T(n/2)+\Theta (n)$, so $T(n)=\Theta (n\log n)$ by the tree above, and this is a worst-case bound: no input makes mergesort slow, because the split does not look at the data. Counting comparisons exactly for $n$ a power of two gives a worst case of $n{\log }_{2}n-n+1$, which is 17 for $n=8$, 49 for $n=16$, and about 18.9 million for a million elements. The best case, on input where every merge exhausts one side first, is $(n{\log }_{2}n)/2$, so the spread between best and worst is only a factor of two.

Mergesort is stable if the merge prefers the left run on ties, and that is the standard implementation. Its cost is memory: the merge cannot be done in place without either extra space or a much more complicated algorithm, so the usual version allocates a second array of size $n$. In-place merging exists but the known methods are slow enough in constant factors that libraries prefer paying the memory.

Example. Merge the sorted runs 2, 5, 8, 13 and 1, 3, 9, 11. How many comparisons does it take, and what is the fewest a merge of two four-element runs could take?

Comparing fronts: 2 against 1 emits 1; 2 against 3 emits 2; 5 against 3 emits 3; 5 against 9 emits 5; 8 against 9 emits 8; 13 against 9 emits 9; 13 against 11 emits 11; and the left run's 13 is copied without a comparison. Seven comparisons, which is the maximum $m-1=8-1$. The minimum is four, achieved when one run is entirely smaller than the other, as with 1, 2, 3, 4 and 5, 6, 7, 8: four comparisons exhaust the left run and the right is copied wholesale.

Now you. How many comparisons does mergesort make in the worst case on 16 elements, and how many on a million?

The same idea elsewhere

Divide and conquer is not a sorting technique, and the clearest evidence is a problem with no order in it at all.

Multiplying two $n$-digit numbers by the method taught in school costs $\Theta (n^2)$ digit multiplications. In 1960 Andrey Kolmogorov conjectured in a seminar that $\Theta (n^2)$ was optimal; within a week the 23-year-old Anatoly Karatsuba had refuted him.

Split each number into halves: $x=a\cdot {10}^m+b$ and $y=c\cdot {10}^m+d$ with $m=n/2$. Then

which needs four half-size multiplications: $ac$, $ad$, $bc$, $bd$. That gives $T(n)=4T(n/2)+\Theta (n)$, and $n^{{\log }_{2}4}=n^2$, so case one of the master theorem returns $\Theta (n^2)$: no gain, which is expected, since this is the school method rearranged.

Karatsuba's observation is that the middle term can be had for one multiplication rather than two, because

so $ad+bc=(a+b)(c+d)-ac-bd$, and $ac$ and $bd$ are already being computed. Three half-size multiplications suffice, with some extra additions, giving $T(n)=3T(n/2)+\Theta (n)$ and $T(n)=\Theta (n^{{\log }_{2}3})=\Theta (n^{1.585})$.

Example. Multiply $1234\times 5678$ by Karatsuba, splitting each into two-digit halves.

Here $a=12$, $b=34$, $c=56$, $d=78$, and $m=2$. The three products are $ac=12\times 56=672$, $bd=34\times 78=2652$, and $(a+b)(c+d)=46\times 134=6164$. The middle term is $6164-672-2652=2840$. Assembling, $672\times {10}^4+2840\times {10}^2+2652=6\{,\}720\{,\}000+284\{,\}000+2652=7\{,\}006\{,\}652$, which is the right answer, using three two-digit multiplications instead of four.

Now you. Multiply $3141\times 2718$ the same way.

Be honest about the size at which this pays. The extra additions and the recursion overhead mean Karatsuba loses to the school method on small numbers, and library implementations such as GMP switch over somewhere around 300 to 2500 bits depending on the machine. At 4096 bits, the size of a large RSA key, the asymptotic gap is a factor of about 32, and there it is decisive.

What mergesort still costs

Mergesort delivers a guaranteed $\Theta (n\log n)$ and stability, and it charges $\Theta (n)$ extra memory for them. For a million records that is another eight megabytes, which is usually irrelevant; for sorting a large fraction of available memory, or on an embedded device, it is not.

The next lesson takes the opposite trade. It partitions the array in place, spending no extra memory beyond the recursion stack, and it is measurably faster than mergesort on real hardware because it moves data less and touches memory more sequentially. What it gives up is the guarantee: its worst case is quadratic, and the reason that rarely matters is a probability argument rather than a proof about the algorithm alone.

Mergesort guarantees $\Theta (n\log n)$ and pays for it with a second array the size of the first, and quicksort is the trade in the other direction.

Partition

The idea is to divide the work before the recursion rather than after it. Choose one element as the pivot and rearrange the array so that everything not greater than the pivot comes first, then the pivot, then everything greater. The pivot is now in its final sorted position, and the two sides can be sorted independently with no combination step at all: no merge, no extra array.

The Lomuto scheme does this in one pass. Take the last element as pivot. Keep an index $i$ marking the end of the small region, initially before the start. Sweep $j$ across the rest; whenever $a[j]$ is not greater than the pivot, advance $i$ and swap $a[i]$ with $a[j]$. At the end, swap the pivot into position $i+1$. The invariant is that $a[\mathrm{0..}i]$ holds elements not greater than the pivot and $a[i+\mathrm{1..}j-1]$ holds elements greater.

Partitioning $n$ elements costs exactly $n-1$ comparisons and at most $n$ swaps, and uses no memory beyond a few indices.

Example. Partition 7, 2, 9, 4, 1, 6, 8, 3 with the last element as pivot, using Lomuto. Show the array after each swap.

The pivot is 3 and $i$ starts at $-1$. At $j=0$, $7>3$, nothing. At $j=1$, $2\le 3$, so $i$ becomes 0 and $a[0]$ swaps with $a[1]$: 2, 7, 9, 4, 1, 6, 8, 3. At $j=2$ and $j=3$, 9 and 4 both exceed 3. At $j=4$, $1\le 3$, so $i$ becomes 1 and $a[1]$ swaps with $a[4]$: 2, 1, 9, 4, 7, 6, 8, 3. At $j=5$ and $j=6$, 6 and 8 exceed 3. Finally the pivot swaps into position $i+1=2$: 2, 1, 3, 4, 7, 6, 8, 9. Seven comparisons, three swaps, and 3 is in its final place.

Now you. Partition 5, 8, 1, 3, 9, 2, 7, 4 the same way.

The other standard scheme is Hoare's, from his original 1961 papers: two indices walk inward from the ends, each stopping at an element belonging on the other side, and the two are swapped. It does about three times fewer swaps than Lomuto and behaves far better on arrays containing many equal keys, which is why library implementations use it or a three-way variant of it. Lomuto is presented here because its invariant is easier to state, not because it is better.

Quicksort, and its two extremes

Quicksort is partition plus recursion: partition, then sort the part left of the pivot and the part right of it. The base case is a range of one element or none.

If the pivot always lands in the middle, the recurrence is $T(n)=2T(n/2)+\Theta (n)$, the same as mergesort's, giving $\Theta (n\log n)$.

If the pivot always lands at one end, the two subproblems are of size $0$ and $n-1$, and

with about $n^2/2$ comparisons: 500 billion on a million elements, some eight minutes, against a fiftieth of a second.

The worst case is not a remote possibility, and this is the part that matters in practice. With the last element as pivot, an already sorted array produces exactly this behaviour: the pivot is the maximum every time. So does a reverse-sorted array, and so does an array of identical values under a naive two-way partition. Sorted input is the most common input shape there is. A textbook quicksort is therefore quadratic on exactly the data people feed it, and it also recurses $n$ deep, which overflows the call stack long before it finishes.

The average case

Between the extremes, the behaviour is far closer to the good end than intuition suggests, and the derivation is worth doing.

Assume all $n!$ orderings of distinct elements are equally likely, so the pivot is equally likely to be the $k$-th smallest for each $k$ from 1 to $n$. Partitioning costs $n-1$ comparisons and leaves subproblems of size $k-1$ and $n-k$. So the expected comparison count satisfies

The sum contains every $C(0)$ through $C(n-1)$ exactly twice, so it simplifies to $C(n)=(n-1)+\frac{2}{n}\sum _{j=0}^{n-1}C(j)$. Solving it, by multiplying through by $n$, subtracting the same equation for $n-1$ and telescoping, gives the exact closed form

where $H_n=1+\frac{12}{+}\frac{13}{+}\cdots +\frac{1}{n}$ is the harmonic number. Since $H_n\approx \ln n+0.5772$, this is asymptotically $2n\ln n\approx 1.386n{\log }_{2}n$.

Put numbers on it. For a million elements the formula gives 24.8 million comparisons. Mergesort's worst case is 18.9 million. So quicksort makes about 31 per cent more comparisons on average, and by the time $n$ is large enough for the lower-order terms to fade, about 39 per cent more.

That is the whole cost, and quicksort is still typically faster than mergesort in practice. The reasons are all outside the comparison count: it moves each element about a third as often, it writes into the array it is already reading rather than into a second one, its inner loop is a sequential scan that the hardware prefetcher predicts perfectly, and it allocates nothing. This is a clean example of the warning from the second lesson: two algorithms with the same asymptotic class can differ by a factor of two or three on constants alone, and the count does not see it.

Example. Using $C(n)=2(n+1)H_n-4n$ with $H_{1000}\approx 7.485$, how many comparisons does quicksort average on 1000 elements, and how does that compare with $n{\log }_{2}n$?

$C(1000)=2\times 1001\times 7.485-4000=14\{,\}985-4000=10\{,\}985$ comparisons. Meanwhile $n{\log }_{2}n=1000\times 9.966=9966$. Quicksort averages about 10 per cent more at this size, and the gap widens slowly towards 39 per cent as $n$ grows, because the $-4n$ term fades relative to $2n\ln n$.

Now you. With $H_{100}\approx 5.187$, how many comparisons does quicksort average on 100 elements?

Randomising the pivot

The average-case result assumed a random input, which is an assumption about the world and therefore not a guarantee. The fix is to stop assuming and start enforcing: choose the pivot uniformly at random from the range being partitioned, and swap it to the end before partitioning.

That single change moves the randomness from the input to the algorithm. The expected cost is now $2(n+1)H_n-4n$ for every input, including sorted ones, because the analysis no longer depends on the arrangement of the data at all. There remains a worst case, but no adversary who does not see the random numbers can arrange for it.

How unlikely is bad behaviour? A random pivot falls between the 25th and 75th percentile with probability $1/2$, and such a split leaves the larger side with at most $3/4$ of the elements. So on any root-to-leaf path, about half the splits are "good", and ${\log }_{4/3}{10}^6=48$ good splits suffice to reduce a million elements to one. The recursion depth is therefore $O(\log n)$ with overwhelming probability. Getting the quadratic case requires near-extreme pivots almost every time for a million consecutive independent choices, and the probability is far below any risk that is worth engineering against.

The cheap alternative is median of three: take the median of the first, middle and last elements as pivot. It makes sorted input into a best case rather than a worst case and costs almost nothing, and it is what most implementations did for decades. It is not a guarantee. In 1999 Doug McIlroy published A Killer Adversary for Quicksort, a comparison function that watches which comparisons a median-of-three quicksort makes and answers them so as to force the quadratic case, without ever contradicting itself. Any deterministic pivot rule can be defeated this way, which matters when the data comes from an untrusted source: a service that sorts user-supplied input with a deterministic quicksort can be brought down by a carefully chosen request. That is why randomisation, or a hard fallback, is the right answer and median-of-three alone is not.

The hard fallback is introsort, published by David Musser in 1997 and now the basis of std::sort. It runs quicksort but counts the recursion depth, and if it exceeds about $2{\log }_{2}n$ it abandons quicksort for heapsort on that subrange. The result has quicksort's speed in the ordinary case and heapsort's $\Theta (n\log n)$ guarantee in every case. Below a threshold of around 16 elements it switches again, to insertion sort, for the reason established two lessons ago. Practically every industrial sort is a hybrid of three algorithms, and it is worth knowing that none of them ships in the pure form taught here.

The same partition, used once

Partitioning is useful on its own, because it answers a question that does not require a full sort. Finding the $k$-th smallest element of an unsorted array is the selection problem, and $k=n/2$ is the median.

The obvious route is to sort and index, costing $\Theta (n\log n)$. But after one partition, the pivot sits at some index $p$, and you know immediately which side the answer is on: if $p=k$ you are done; if $k<p$ the answer lies to the left; otherwise to the right. So recurse into one side only. That is quickselect, Hoare's, from the same 1961 work.

With balanced splits the recurrence is

because the level costs form a geometric series $n+n/2+n/4+\cdots <2n$ rather than staying constant. The expected comparison count with random pivots is $2n$ for finding the minimum and about $2(1+\ln 2)n\approx 3.39n$ for the median. Linear, with a small constant, to find the median of an unsorted array without sorting it.

The worst case is still $\Theta (n^2)$, and here there is a genuine repair rather than just a probabilistic one: the median-of-medians algorithm of Blum, Floyd, Pratt, Rivest and Tarjan (1973) picks a pivot guaranteed to be between the 30th and 70th percentiles, giving worst-case $\Theta (n)$. Its constant is large enough that it is rarely used directly, and its usual role is as the fallback inside a randomised implementation.

Example. Using the partition performed in the first example, which left 2, 1, 3, 4, 7, 6, 8, 9 with the pivot 3 at index 2, find the 3rd smallest element.

The 3rd smallest is at index 2 in 0-based terms, and the pivot is exactly there. So the answer is 3, found after a single partition and seven comparisons, with no sorting of either side. Had the target been index 5, the search would continue into the right part 7, 6, 8, 9 only, discarding the other three elements permanently.

Now you. Using the second partition, 1, 3, 2, 4, 9, 5, 7, 8 with pivot 4 at index 3, find the 5th smallest element.

Where this leaves sorting

There are now two $\Theta (n\log n)$ sorts with opposite trades: mergesort, guaranteed and stable and hungry for memory; quicksort, in place and faster in practice and guaranteed only once randomised or bounded by a fallback.

Neither is meaningfully below $n{\log }_{2}n$ comparisons, and mergesort's worst case of $n{\log }_{2}n-n+1$ is suspiciously close to the $n{\log }_{2}n$ that the shape suggests. That raises a question the course can now actually answer: is $n\log n$ the end of the road, or just the best anybody has managed? The next lesson proves it is the end of the road for every algorithm that sorts by comparing, and then shows two algorithms that finish in linear time by not comparing.

Mergesort's worst case is $n{\log }_{2}n-n+1$ comparisons, which is close enough to $n{\log }_{2}n$ to raise the question of whether anything can do better.

That question has an answer, and it is unusual in this course because it is a statement about every possible algorithm rather than about one. It says that a whole family of sorts is stuck where mergesort already is, and it says exactly why. Then it points at the escape, which is to stop being a member of that family.

What a comparison sort is allowed to know

Every sort so far, selection, insertion, bubble, merge and quicksort, learns about the input in exactly one way: it picks two elements and asks which is smaller. It never looks at a key's value, never does arithmetic on it, never uses it as an address. Such an algorithm is a comparison sort, and the restriction is not artificial: it is what lets one sorting routine work on integers, strings, dates and user-defined records alike, given only a comparison function.

Fix $n$ and consider all the ways the input could be arranged. If the elements are distinct there are $n!$ arrangements, and each one requires a different sequence of moves to put right. The algorithm must produce the right permutation for every one of them, and the only information it ever receives is the yes-or-no answers to its comparisons.

So the run of the algorithm on any particular input is a path through a decision tree. Each internal node is a comparison, "is $a_i<a_j$?", with two branches. Each leaf is the point at which the algorithm stops and outputs an ordering. Two inputs that give the same answers to every comparison follow the same path and reach the same leaf, so they get the same output. If those two inputs needed different outputs, the algorithm is wrong on at least one of them.

That is the entire argument in one sentence: a correct comparison sort needs at least $n!$ distinct leaves, one for each permutation it might have to undo.

Counting the depth

A binary tree of height $h$ has at most $2^h$ leaves, because each level at most doubles the count. Needing $L$ leaves therefore forces $h\ge {\log }_{2}L$. With $L=n!$,

and $h$ is the number of comparisons made on the longest path, which is the worst case. So no comparison sort, existing or yet to be invented, can sort $n$ elements in fewer than ${\log }_2(n!)$ comparisons in the worst case.

Now put a size on ${\log }_2(n!)$. Stirling's approximation gives $n!\approx \sqrt{2\pi n}(n/e{)}^n$, and taking logarithms,

Since ${\log }_{2}e=1.4427$, the bound is $n{\log }_{2}n-1.4427n$ plus a term that grows only logarithmically. For a million elements that is 19,931,569 minus 1,442,695, so about 18,488,900 comparisons. Mergesort's worst case on the same input is 18,931,570. Mergesort is within 2.4 per cent of a bound that applies to every comparison sort that will ever be written. There is nothing significant left to win.

Example. What is the smallest number of comparisons that could possibly sort five elements, and is it achievable?

There are $5!=120$ orderings, and ${\log }_{2}120=6.907$, so at least seven comparisons are needed, since a comparison count is a whole number. Seven is achievable: the merge insertion algorithm of Ford and Johnson (1959) sorts five elements in seven comparisons, and so does the more ordinary route of sorting the first two, inserting the third by binary search, and continuing. So the bound is tight here.

Now you. How many comparisons are needed at minimum for eight elements, and for ten?

What the bound does not say

The result is often quoted as "sorting is $n\log n$", which is wrong in three separate ways, and each of them matters.

It is not exact. The counting argument gives a floor, not a construction, and the floor is sometimes unreachable. For twelve elements ${\log }_2(12!)=28.84$, so the bound says 29, yet Mark Wells showed by exhaustive search in 1965 that 30 comparisons are genuinely required and 29 is impossible. The information count says how much has to be learned; it does not promise that comparisons can be arranged to learn it that efficiently.

It bounds comparisons, not time. An algorithm making the minimum number of comparisons can still be slow, because comparisons are not the only cost. Mergesort and quicksort make comparison counts within 40 per cent of each other and differ in running time by more, in quicksort's favour, entirely through data movement and memory access. A count of comparisons is a good proxy, not the thing itself.

It bounds the worst case over all inputs, which leaves the door open for inputs that are not arbitrary. If the array is already sorted, insertion sort finishes in $n-1$ comparisons, far below ${\log }_2(n!)$, and there is no contradiction: that algorithm still needs a deep tree for the inputs it has not been given. Adaptive sorts exploit exactly this. Timsort, which ships in Python and in Java for objects, finds runs that are already ordered and merges them, so it costs $\Theta (n)$ on sorted or reverse-sorted input and $\Theta (n\log n)$ at worst.

The average case is bounded too, and by essentially the same amount. The average number of comparisons is the average leaf depth of the tree, and a binary tree with $n!$ leaves has average depth at least ${\log }_2(n!)$ minus a constant. So a comparison sort cannot be fast on average either. Randomising the input does not help; the bound holds regardless.

Not comparing

Every step of the argument used the assumption that the algorithm's only access to the data is through comparisons. Break that assumption and the bound simply does not apply.

Suppose the keys are integers from 0 to $k-1$. Then a key can be used as an array index, and indexing is not a comparison. Counting sort does this. Make an array $C$ of $k$ counters. Sweep the input once, incrementing $C[x]$ for each key $x$. Replace $C$ by its running totals, so that $C[v]$ holds the number of keys less than or equal to $v$, which is the position just past where the last $v$ belongs. Then sweep the input backwards, placing each key at position $C[x]-1$ and decrementing $C[x]$.

The cost is $\Theta (n+k)$: two passes over $n$ elements and one over $k$ counters. When $k$ is comparable to $n$ this is linear, and it beats every comparison sort by a factor of $\log n$. The backwards final sweep is what makes it stable, which is the property the next algorithm depends on entirely.

The catch is $k$. Sorting a million 32-bit integers this way needs $2^{32}$ counters, sixteen gigabytes, to sort four megabytes of data. Counting sort is for small key ranges: exam marks, ages, bytes, priority levels.

Example. Counting-sort the marks 3, 1, 4, 1, 5, 0, 2, 3, 1, 4, where marks run from 0 to 5. Show the counters and the total work.

Counts: 0 appears once, 1 three times, 2 once, 3 twice, 4 twice, 5 once, so $C=[1,3,1,2,2,1]$. Running totals: $C=[1,4,5,7,9,10]$. Reading those, the single 0 goes to position 0, the three 1s to positions 1 to 3, the 2 to position 4, and so on, giving 0, 1, 1, 1, 2, 3, 3, 4, 4, 5. The work is $n+k=10+6=16$ operations, against the 22 comparisons that the counting bound says any comparison sort needs for ten elements.

Now you. Counting-sort 2, 5, 3, 0, 2, 3, 0, 3 over the same range 0 to 5.