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

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).
13 min read 6 figures The figure is the runTwo counts, two rankings

The instrumented array records more than counters. It records the complete sequence of indices touched, in order.

That sequence is a much richer object than any count derived from it. Plotted as index against time it becomes a picture, and the pictures for different algorithms are so distinct that a sorting algorithm can be identified from its trace at a glance — which is a strange thing to be able to say about a quantity that every complexity analysis discards entirely.

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. 1 Every array access from one run of each algorithm on 256 random elements. Time runs left to right; array index runs bottom to top. Merge sort makes 49% of its accesses to the next element or the same one. Heapsort makes 14%. Both are Θ(n log n), both were counted by the same instrument, and no number in the comparison count distinguishes these two pictures.

Reading the pictures

Merge sort produces bands. Each merge sweeps two ascending runs and writes an ascending output, so within a merge the accesses climb steadily. The bands get wider and fewer as the recursion unwinds: many short sweeps at the bottom, a single full-length one at the top. The whole picture is made of straight ascending strokes.

Heapsort produces a spray with a descending upper edge. The sift-down operation walks from a node to a child at roughly twice the index, so a single sift-down jumps by a doubling sequence — a scatter across the whole array in log⁡n\log n steps. The descending edge is the sorted region growing at the top as elements are extracted, one per iteration.

Quicksort produces a narrowing triangle. Each partition sweeps two pointers towards each other across a contiguous range, and each recursive call halves the range. The picture is a nested set of sweeps, each half the width of its parent, with the widest at the start.

Insertion sort produces a diagonal band. The outer loop advances one element at a time and the inner loop walks backwards a short distance, so the trace hugs the diagonal with a small vertical thickness that is the average displacement.

These shapes are not decoration. Each one is a direct statement about how the algorithm will behave against a memory hierarchy, and they say things the counts do not.

Sequentiality, and what it misses

The single-number summary of a trace used on this site is sequentiality: the fraction of consecutive accesses that go to the same element or the next one. It is the pattern a prefetcher can follow.

algorithm sequentiality at n = 2,048
bubble sort 75%
insertion sort 67%
merge sort with cutoff 54%
merge sort 49%
quicksort, random pivot 39%
quicksort, median of three 37%
Shellsort 30%
heapsort 14%
selection sort 0%

The bottom row is the measure failing, and it is worth understanding why rather than quietly dropping it.

Selection sort’s inner loop compares each element against the running minimum. The comparison primitive records two accesses — the candidate at index jj and the minimum at index mm — so the trace alternates j,m,j+1,m,j+2,m,…j, m, j{+}1, m, j{+}2, m, \ldots. No consecutive pair is adjacent, so the measure reports zero, while the algorithm is in fact walking straight through the array and touching one fixed extra location. Its real locality is excellent.

The measure is looking at consecutive pairs and the algorithm’s structure is a stride-two pattern with a stationary component. A better measure would consider a window rather than a pair. The site keeps the simple one and reports the miss count alongside, because the miss count does not have this blind spot: selection sort’s misses are high for a different and genuine reason, which is that it makes twice as many accesses as anything else quadratic.

The general lesson is one this site keeps running into: a summary statistic has a shape it cannot see, and the way to find out is to look at the thing it summarises. That is what the trace pictures are for.

Why recursion is good for locality

The divide-and-conquer algorithms have an advantage that is not in their operation counts and is visible in their traces.

After a few levels of recursion, the subproblem being worked on is small. Once it is smaller than the cache, everything below that level runs entirely at cache speed — and most of the work is below that level, because each level does the same total work and there are many more small subproblems than large ones.

The striking part is that this happens without the algorithm knowing anything about the cache. A recursive algorithm that halves its problem passes through every scale on the way down, so whatever the cache’s capacity is, some level of the recursion matches it. This is the idea behind cache-oblivious algorithms: structure the recursion so that it is automatically efficient at every level of a memory hierarchy whose parameters are never learned. Merge sort gets it for free.

Heapsort cannot. Its working set is the entire heap from the first operation to the last, and there is no level at which it becomes small. That is why its miss count is 3.7 times merge sort’s on 1.9 times the comparisons, and it is a structural property of maintaining one global structure rather than a fixable inefficiency — the same structural cost that an unbalanced tree pays on every lookup.

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. Quicksort, median of three makes 39% of its accesses to the next element or the same one; Insertion sort makes 66%. That difference is invisible in the comparison count and is most of what the machine feels.Quicksort39% sequential · 6,999 accesses2560Insertion sort66% sequential · 46,947 accesses2560time (accesses, left to right) · index (bottom to top)one run each, n = 256every access plotted
Fig. 2 Quicksort against insertion sort. Quicksort’s narrowing triangle is the recursion descending — each partition works on a contiguous range half the width of its parent, so the working set shrinks automatically. Insertion sort’s band hugs the diagonal: it never looks far from where it is, which is why an algorithm this expensive in comparisons is nonetheless friendly to memory.

Insertion sort’s compensation

The trace explains something the comparison count makes look absurd.

Insertion sort at n = 2,048 performs 1,058,128 comparisons against merge sort’s 19,919 — 53 times as many. It is a bad algorithm by that measure and the measure is not wrong.

But 67% of its accesses are sequential, and its working set at any moment is a handful of adjacent elements. Every access is to the element beside the last one. In a cache-line model this is nearly free: eight elements arrive per fetch and all eight are used before the next fetch.

So insertion sort converts a large comparison count into a small number of expensive events, which is exactly the trade modern hardware rewards. On small arrays this is enough to make it the fastest thing available despite doing far more nominal work — and the crossover is measurable, though not in the count everyone assumes.

Bubble sort has the best sequentiality of anything here, at 75%, and it is still a bad algorithm, because it combines good locality with 2,091,472 comparisons and 62,563 swaps. Locality is a multiplier on the cost of an operation, not a substitute for doing fewer of them.

The trace and the count, side by side

The most direct way to see what a trace adds is to put it next to the count it is not.

Insertion sort and bubble sort at n=2,048n = 2{,}048 perform 1,058,128 and 2,091,472 comparisons — bubble sort does about twice the work by that measure, and both are quadratic. Their traces are nearly the same picture: both hug the diagonal, both have high sequentiality (67% and 75%), and their modelled miss counts are 103,343 and 246,592, which is the same factor of two the comparison count gave.

So for these two algorithms the trace adds nothing. The counts and the locality agree, the ratio is the same by either measure, and a comparison count would have said everything.

Merge sort and heapsort are the opposite. 19,919 comparisons against 38,765 — a factor of 1.9 — and 1,277 misses against 4,677, a factor of 3.7. The trace is carrying something the count is not, and that something is worth about twice again.

The general rule that falls out: the trace matters when the algorithms differ in structure and not when they differ only in constant. Two nested loops over an array look alike whatever the loops do. A recursion and a heap traversal do not.

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. Insertion sort makes 66% of its accesses to the next element or the same one; Bubble sort makes 76%. That difference is invisible in the comparison count and is most of what the machine feels.Insertion sort66% sequential · 46,947 accesses2560Bubble sort76% sequential · 126,750 accesses2560time (accesses, left to right) · index (bottom to top)one run each, n = 256every access plotted
Fig. 3 The case where the trace adds nothing. Insertion sort and bubble sort produce nearly the same picture — both hug the diagonal, both are highly sequential, and their miss counts stand in the same ratio as their comparison counts. When two algorithms share a structure, the count is sufficient.

What a trace is for

Three uses beyond producing pretty pictures.

Feeding the cache model. The trace is the input to the miss count, which is the second independent quantity this site carries. Without the trace there is only one number and no way to notice that it is insufficient.

Diagnosing where an algorithm is slow. A trace shows which phase of an algorithm scatters. If merge sort were slower than expected, the trace would say whether the problem is in the merges or in the copy back from the buffer, and it says so by where on the picture the scattering is rather than by a summary number that mixes them.

Making the invisible visible. The strongest argument for these pictures is that nobody who has seen the heapsort trace beside the merge sort trace goes on believing that “both are Θ(nlog⁡n)\Theta(n \log n)” is a complete description. The classification is true and it is missing this, and there is no way to convey what it is missing except by drawing it.

Heapsort on 24 random elements, six moments from one runEach panel is the array as it actually stood after a particular write, sampled evenly across the 95 writes the run performed. The comparison counter beside each panel is the counter at that instant, so the picture and the numbers come from the same execution. The run finished at 151 comparisons and 95 swaps.after 0 writes0 cmpafter 19 writes44 cmpafter 38 writes74 cmpafter 57 writes101 cmpafter 76 writes130 cmpafter 95 writes151 cmprandom input, seed stated in lib/count.js151 comparisons in this run
Fig. 4 A different kind of trace, on the same principle: heapsort on 24 elements, six moments from one run, with the comparison counter at each instant. The heap-building phase leaves the array in an order that looks random and is not — it satisfies the heap property — and then the extraction phase builds the sorted region down from the top.

What the pictures do not show

Three limitations worth stating, since a picture is more persuasive than a number and deserves more scepticism.

The traces are at n = 256. At that size the entire array fits comfortably in any real cache, so a real machine would show none of the effects these pictures are used to explain. The pictures are illustrating a structure that persists at every size, and the structure is what the cache model at larger sizes actually measures.

The vertical axis is an array index, not an address. Two adjacent indices are adjacent in memory only for a contiguous array of fixed-size elements. For an array of pointers to objects — which is what sorting objects in most languages means — the indices are adjacent and the objects are wherever the allocator put them, and every comparison chases a pointer to somewhere unrelated. The pictures describe the index trace and the hardware sees the address trace, and for a pointer array the two have very little to do with each other.

One run, one seed. Each picture is a single execution on a single input, and a single run is not a distribution. For the deterministic algorithms that is the whole story; for randomised quicksort it is one draw, and a different seed gives a visibly different triangle. The site’s figures state their seeds for this reason.

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. 5 The traces reduced to two numbers each, at a size where the cache model has something to say. What the pictures show qualitatively — heapsort scattering, quicksort sweeping — is the same information that puts these points off a single line, which is the quantitative form of the argument.

The measure that would be better

Since the sequentiality measure has a known blind spot, it is worth saying what would replace it.

The quantity that actually predicts cache behaviour is reuse distance: for each access, how many distinct lines were touched since that line was last touched. If the reuse distance is smaller than the cache’s capacity in lines, the access hits; otherwise it misses. That is not an approximation — it is exactly what a fully associative LRU cache does, so a reuse-distance histogram determines the miss count at every possible cache size at once.

The site computes miss counts directly by simulating, which is equivalent and simpler to implement, and reports sequentiality alongside because it captures a different thing: whether a prefetcher could help. Two accesses can both hit and still differ in whether the hardware fetched them ahead of time.

The two measures answering different questions is the same pattern as comparisons and misses answering different questions, one level down. There is no single number, and every level of the analysis discovers this again.

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 What the reuse distances of a random access pattern look like when summarised into a miss rate, against the size of the region being accessed. The cliff is where the typical reuse distance crosses the capacity. Every trace on this page has its own version of this curve, and the shape of the trace is what determines it.

Where this goes next

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 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. 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. comparisonsswapsInsertion sort63,071 / 0Selection sort130,816 / 504Bubble sort129,688 / 62,563Merge sort3,964 / 0Heapsort7,653 / 4,170Quicksort5,049 / 2,380n = 512, random inputcounted in the same run One run, four counts, four answers The question “how many operations” has no answer until the operation is named. Selection sort makes more comparisons than any other algorithm here and fewer writes than almost all of them; bubble sort matches its comparisons and does 124 times the swapping. The ranking depends entirely on which count is chosen, and the choice needs justifying.