Algorithms & Data Structures
the bound is a claim, and it is checkable
What the machine does

The count is not the time

An operation count is exact, machine-independent, and not a running time. The gap between them is mostly memory, and it is large enough to reorder the rankings. This site carries a second count — modelled cache misses from the same runs — and asserts that the two disagree, because if they agreed the second one would carry no information.
14 min read 6 figures Two counts, two rankingsMeasured, not asserted

Every number in the counting and floors fields on this site is exact and none of them is a duration.

The distance between the two is not a small correction. On modern hardware a comparison whose operands are already in the processor’s fastest cache costs well under a nanosecond; one that has to be fetched from main memory costs on the order of a hundred. Two orders of magnitude, decided not by how many operations an algorithm performs but by where in memory it performs them.

An algorithm doing half the comparisons in a worse order is routinely slower. Nothing in a comparison count reveals that, and no amount of counting comparisons more carefully will.

Comparisons against modelled cache misses, n = 2048One point per algorithm, both axes logarithmic. If the comparison count determined the memory behaviour the points would fall on a line, and they do not: Merge sort and Quicksort, median-3 and Merge + cutoff sit at least two places apart in the two rankings. Cache model: fully associative · 64 lines × 8 elements · LRU. The vertical axis is a modelled miss count, not a time.10⁵10⁶10³10⁴10⁵comparisonscache misses (modelled)Insertion sortSelection sortBubble sortMerge sortHeapsortQuicksort, firstQuicksort, median-3Quicksort, randomShellsortMerge + cutofffully associative · 64 lines × 8 elements · LRUa modelled count, not a time
Fig. 1 Comparisons against modelled cache misses, one point per sorting algorithm at n = 2,048, both axes logarithmic. If the comparison count determined the memory behaviour these points would lie on a line. They do not: several algorithms sit at least two places apart in the two rankings, which is the entire justification for carrying a second quantity.

What is actually happening in the machine

The relevant fact about modern hardware is that memory is not one thing. It is a hierarchy, and the levels differ by orders of magnitude in both size and speed.

Registers hold a few dozen values and are instant. The first-level cache holds tens of kilobytes and costs a few cycles. The second and third levels hold megabytes and cost tens of cycles. Main memory holds gigabytes and costs a couple of hundred. The ratios have widened steadily for four decades, because processors have got much faster and memory latency has barely moved.

Two consequences shape everything below.

Memory moves in lines, not elements. Fetching one byte from main memory fetches a whole aligned block, typically 64 bytes — eight double-precision numbers, or sixteen 32-bit integers. An algorithm that uses all of them has amortised the fetch sixteen ways. One that uses a single element and moves on has paid for sixteen and used one.

The hardware guesses. A prefetcher watches the stream of addresses and, when it detects a regular pattern, fetches ahead of the program. An algorithm walking straight through an array gets its data before it asks for it. An algorithm jumping unpredictably gets nothing.

So the property that matters is locality: does the algorithm touch memory in an order the machine can anticipate? And that property is invisible to every count in the counting field.

The model

This site does not time anything. What it does instead is record the complete sequence of array indices each run touches — the instrumented array collects it alongside the counters — and replay that trace through an explicit cache model.

The model is deliberately simple and its parameters are printed on every figure that reports a number from it:

  • fully associative — any line may live in any slot
  • a stated number of lines, each holding a stated number of elements
  • least-recently-used replacement

A real cache is set-associative, has several levels, has separate instruction and data paths, has write buffers, and prefetches. This model has none of that. What it does capture is the thing that explains most of the effect: whether the working set fits, and whether consecutive accesses land in the same line.

It does not produce a time and no essay here treats its output as one. The output is a count of modelled misses. It is a second exact, reproducible, machine-independent number, and its value is that it is independent of the first one.

The model is checked in both directions

A model that reported plausible numbers without measuring anything would be worse than no model, because every comparison drawn from it would be written as though it worked.

So the gate makes four demands.

A sequential walk must miss exactly once per line. Walking 4,096 elements with eight elements per line must produce exactly 512 misses. Not approximately — exactly. If it produced more, the model would be wrong about the only access pattern hardware is unambiguously good at, and every comparison would be biased in the same direction.

A random walk over an oversized array must miss almost always. Over an array eight times the cache’s capacity, the measured miss rate is 87%. A model that reported something similar for both patterns would be measuring nothing.

Two traces of identical length must give very different miss counts. A sequential walk of 2,048 accesses produces 256 misses; a stride-97 walk of the same 2,048 accesses produces 2,048. A factor of eight. If those numbers were close, the miss count would be a restatement of the access count and this site’s two-quantity framing would be empty.

And the model must be capable of failing that test. The gate runs the independence check with a line size of one element — a cache with no spatial locality to exploit — and requires it to fail, because under that configuration the second count genuinely does stop carrying information.

4,096 accesses, five ordersEvery row performs exactly 4,096 array accesses — the same count an operation-counting analysis would assign them all — and the modelled miss counts differ by a factor of 8. Reading backwards is as cheap as reading forwards, because a cache line is a line whichever end you enter it from. Stepping by 8 elements touches a new line every time and is as expensive as random. Model: fully associative · 32 lines × 8 elements · LRU.cache missesstraight through512100% sequentialbackwards5120% sequentialevery 8th element4,0960% sequentialevery 97th element4,0960% sequentialuniformly random3,8460% sequentialfully associative · 32 lines × 8 elements · LRU8× between best and worst order
Fig. 2 The independence check, drawn. Five access patterns over 4,096 elements, each performing exactly the same number of accesses. Reading backwards is as cheap as reading forwards, because a cache line is a line whichever end it is entered from. Stepping by eight touches a new line every time and is as expensive as random. The count is fixed at 4,096 in every row, and the misses differ by a factor of eight.

What the second count says about the sorts

At n = 2,048 on random input, with 64 lines of 8 elements:

algorithm comparisons modelled misses sequential
merge sort 19,919 1,277 49%
merge sort with cutoff 23,497 1,277 54%
quicksort, median of three 25,703 1,187 37%
quicksort, random pivot 25,112 1,261 39%
heapsort 38,765 4,677 14%
Shellsort 30,536 3,593 30%
insertion sort 1,058,128 103,343 67%
selection sort 2,096,128 245,740 0%
bubble sort 2,091,472 246,592 75%

Several things here are not visible in the comparison column.

Heapsort’s miss count is 3.7 times merge sort’s, on 1.9 times the comparisons. Heapsort’s problem on real hardware is worse than its comparison count suggests, and the reason is in the last column: 14% of its accesses go to the adjacent element, against merge sort’s 49%. Heapsort moves between a node at index ii and its children at 2i+12i+1 and 2i+22i+2, which for a large heap are far apart in memory. It is the least local algorithm here.

Median-of-three quicksort has the fewest misses of anything — fewer than merge sort, despite 29% more comparisons. Quicksort’s partition sweeps two pointers towards each other through a contiguous range, which is close to the best possible access pattern, and it sorts in place so there is no buffer competing for cache.

That inversion is the whole point. By comparisons, merge sort wins. By modelled misses, quicksort wins. Both numbers are exact and neither is the running time, and anyone choosing between them needs to know which resource is scarce.

Selection sort reports 0% sequential. Its inner loop does walk straight through, but every comparison is against the running minimum at a fixed index, so the trace alternates between a moving position and a stationary one and no consecutive pair is adjacent. This is a case where the sequentiality measure — defined as the fraction of consecutive accesses that go to the same or the next element — understates the locality badly. The miss count is the more trustworthy number and it is high for a different reason: selection sort makes twice as many accesses as anything else quadratic.

What a second count is for

The value of carrying two numbers is not that the second is more accurate. It is that two numbers can disagree, and a disagreement is information that one number cannot contain.

This is the same structure as comparisons and swaps disagreeing about which quadratic sort is better, one level up. There the two counts were both about operations; here one is about operations and the other about where they happen, which makes them independent in a stronger sense.

The strongest form of the point is a case where the two counts give opposite verdicts. Merge sort and median-of-three quicksort at n=2,048n = 2{,}048:

  • merge sort does 19,919 comparisons, quicksort 25,703 — merge sort wins by 29%
  • merge sort incurs 1,277 modelled misses, quicksort 1,187 — quicksort wins by 8%

Neither number is wrong and neither is a time. What they establish jointly is that the choice between these two algorithms depends on which resource is scarce, and a site reporting only the first would have declared merge sort better, full stop.

The site therefore asserts the disagreement rather than merely observing it. A figure requires that ranking by comparisons and ranking by misses give different orders, and that at least one algorithm moves two or more places between them. If the two counts ever became predictable from each other, that assertion would fail and the build would stop — which is the same must-be-able-to-fail discipline applied to a claim about the method rather than about an algorithm.

Where insertion sort actually wins — and it is not in the comparisonsMean over 60 random inputs at each size, both counts on one pair of axes. Insertion sort performs more comparisons than Merge sort at every size measured, including n = 4: the dashed pair never cross. The solid pair — total reads and writes — do cross, between n = 12 and n = 16. The familiar advice to fall back to insertion sort on small subarrays is right, and the reason is memory traffic rather than comparisons, which is a distinction the usual telling of it loses.481632641281010010³10⁴noperations (mean of 60 runs)Insertion trafficMerge trafficInsertion cmpMerge cmptraffic crossessolid: reads + writes · dashed: comparisonstraffic crosses between n = 12 and 16; comparisons never do
Fig. 3 The disagreement in its sharpest form. Insertion sort against merge sort, comparisons dashed and total memory traffic solid. The comparison lines never cross; the traffic lines do. One count says the insertion-sort fallback every standard library implements is pointless, and the other says it is necessary.

What the model cannot establish

Four things, and they are worth being explicit about because a plausible number invites over-reading.

It is not a time. Multiplying misses by a memory latency and adding comparisons times a comparison cost would produce a number. That number would be wrong, because it ignores instruction-level parallelism, out-of-order execution, and the fact that several misses can be in flight at once. Real processors overlap memory stalls with useful work to an extent this model has no way to represent — which is one more reason nothing here is called a time.

It has no prefetcher. This is the largest single omission and it biases against sequential algorithms. A real machine walking straight through an array pays almost nothing, because the hardware fetched the lines before they were needed. The model charges a full miss per line. So insertion sort’s 103,343 misses at n = 2,048 look much worse than they would be — 67% of its accesses are sequential and a real prefetcher would absorb most of that.

It has one level. Real hierarchies have three or four, and an access that misses L1 but hits L2 costs a tenth of one that reaches memory. The model’s binary hit-or-miss flattens a distinction that matters.

Associativity conflicts are absent. A real set-associative cache can evict a line while capacity remains, because too many hot addresses map to the same set. This produces the notorious pathologies where an array stride that happens to be a power of two is catastrophically slower than one that is not. The model, being fully associative, never sees them.

Every one of these makes the model optimistic or pessimistic in a known direction, which is the useful property: the numbers are comparable to each other even where they are not comparable to reality.

Where each algorithm looks, and whenEvery array access from one run of each algorithm on 256 random elements: time along the horizontal axis, array index up the vertical. Merge sort makes 49% of its accesses to the next element or the same one; Heapsort makes 15%. That difference is invisible in the comparison count and is most of what the machine feels.Merge sort49% sequential · 7,540 accesses2560Heapsort15% sequential · 14,044 accesses2560time (accesses, left to right) · index (bottom to top)one run each, n = 256every access plotted
Fig. 4 The underlying data, before it becomes a miss count. Every array access from one run of each algorithm, plotted as index against time. Merge sort’s accesses form sweeps; heapsort’s form a spray. This picture is what the cache model is summarising into a single number, and it contains more than the number does.

The parameters are a choice, and they are printed

A miss count without a line size and a capacity is not a measurement of anything, so every figure on this site that reports one prints both.

The defaults are 64 lines of 8 elements — 512 elements of cache — and they were chosen to put the interesting transitions inside the range of sizes the site can afford to measure. A real last-level cache holds millions of elements, and using a realistic capacity would mean every figure showing a flat line until nn passed a million, which is beyond what the build can compute for a quadratic algorithm.

So the model is scaled down, deliberately, and the scaling is stated. What that preserves is the shape of every effect — the cliff, the difference between sequential and strided, the ranking of algorithms by locality — because all of those depend on the ratio between the data size and the capacity rather than on either absolutely.

What it does not preserve is any number that could be compared against a real machine. This is the same trade as choosing a cost model for comparisons: the model is a lens, it is stated, and the results are interpretable through it and not otherwise.

The cliff: miss rate against working-set sizeTwenty thousand uniformly random accesses into an array of n elements, replayed through a cache holding 256 elements. Below 256 the miss rate is essentially zero; a factor of eight above it, essentially everything misses. The comparison count of an algorithm says nothing about which side of this cliff it is working on, which is why the two counts are carried separately. Model: fully associative · 32 lines × 8 elements · LRU.0%25%50%75%100%645124,09665,536cache holds 256array size n (elements)miss ratefully associative · 32 lines × 8 elements · LRU20,000 random accesses per point
Fig. 5 The same curve with half the capacity. The cliff moves left by a factor of two and its shape is unchanged, which is the property that makes the scaled-down model useful — the transition is a function of data size divided by capacity, so shrinking both leaves the picture intact.

Why not just measure the time

The honest answer is that measuring time properly is a different project.

Doing it well means a quiet machine, many trials, reported distributions, control over frequency scaling and address-space layout randomisation, and a clear statement of which machine. Doing it badly means publishing a number that describes a container that ran for eight seconds in 2026 and inviting readers to compare it against numbers from other pages that describe other containers.

The middle path this site takes is to model the specific mechanism that explains most of the variation, state the model’s parameters everywhere, and never call the output a time. That gives a second exact number that is genuinely independent of the first, which is enough to make the point that one number was never sufficient — and stops short of claims the method cannot support.

Where a time would settle a question, the essays say that a time would settle it and that this site does not have one. The crossover essay is the clearest case: it establishes that the familiar insertion-sort fallback is not about comparisons, and it stops there rather than claiming to know the exact threshold on any particular processor.

The cliff: miss rate against working-set sizeTwenty thousand uniformly random accesses into an array of n elements, replayed through a cache holding 512 elements. Below 512 the miss rate is essentially zero; a factor of eight above it, essentially everything misses. The comparison count of an algorithm says nothing about which side of this cliff it is working on, which is why the two counts are carried separately. Model: fully associative · 64 lines × 8 elements · LRU.0%25%50%75%100%645124,09665,536cache holds 512array size n (elements)miss ratefully associative · 64 lines × 8 elements · LRU20,000 random accesses per point
Fig. 6 Where the whole effect comes from. Miss rate against the size of the array being accessed, with the cache’s capacity marked. Below capacity, essentially everything hits. A factor of eight above it, essentially everything misses. An algorithm’s comparison count says nothing about which side of this cliff it is working on.

Where this goes next

after 0 writes0 cmpafter 32 writes32 cmpafter 64 writes63 cmpafter 95 writes94 cmpafter 127 writes125 cmpafter 159 writes157 cmprandom input, seed stated in lib/count.js157 comparisons in this run Counting instead of timing A stopwatch measures the laptop it runs on. A counter measures the algorithm. Every number on this site comes from an array that increments a tally each time it is read, written, compared or swapped — which makes the counts exact, reproducible to the last digit, and identical on every machine that has ever built this page. 0%25%50%75%100%645124,09665,536cache holds 512array size n (elements)miss ratefully associative · 64 lines × 8 elements · LRU20,000 random accesses per point The cliff where the data stops fitting Below the cache's capacity, almost every access hits. A factor of eight above it, almost every access misses. The transition is not gradual and it is not a property of any algorithm — it is a property of how much data there is, and an algorithm's complexity class says nothing about which side of it a program is working on. Merge sort49% sequential · 7,540 accesses2560Heapsort15% sequential · 14,044 accesses2560time (accesses, left to right) · index (bottom to top)one run each, n = 256every access plotted Where an algorithm looks Plotted as index against time, every array access an algorithm makes becomes a picture that no count contains. Merge sort's is a set of sweeps. Heapsort's is a spray. Quicksort's is a narrowing triangle. These shapes decide how fast the algorithms run and they are entirely absent from the analysis that says all three are Θ(n log n).