Algorithms & Data Structures
the bound is a claim, and it is checkable
Counting

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.
15 min read 7 figures Two counts, two rankingsMeasured, not asserted

Selection sort and bubble sort perform almost exactly the same number of comparisons. At n = 512 on random input the counts are 130,816 and 129,688 — within one percent, and they stay within one percent at every size. By the measure that every introductory course uses to rank sorting algorithms, they are the same algorithm.

They are not the same algorithm. Bubble sort performs 62,563 swaps in that run. Selection sort performs 504.

That is a factor of 124, it is not visible in the comparison count, and if the things being sorted are anything larger than a machine integer it is the number that decides which algorithm was the right one.

Comparisons and swaps at n = 512Selection sort performs the most comparisons of any algorithm here and among the fewest swaps — it never moves an element it does not have to. Ordering these algorithms by comparisons and ordering them by swaps gives two different orders, which is why the question "how many operations" needs the operation named before it has an answer.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
Fig. 1 Comparisons and swaps at n = 512, from the same runs. The two bars in each row are the same algorithm measured two ways. Ordering by the blue bar and ordering by the orange bar produce different orders — which is the entire content of this essay, and the reason the site records four counts rather than one.

The four counts

Every algorithm here runs against an instrumented array whose primitives tally four things:

  • comparisons — how many times two elements were asked which was larger
  • swaps — how many times two elements exchanged places
  • reads — how many times an element was fetched
  • writes — how many times an element was stored

At n = 512 on random input, in full:

algorithm comparisons swaps reads writes
insertion sort 63,071 0 126,145 63,074
selection sort 130,816 504 262,640 1,008
bubble sort 129,688 62,563 384,502 125,126
merge sort 3,964 0 12,536 4,608
heapsort 7,653 4,170 23,646 8,340
quicksort, median of three 5,049 2,380 10,997 4,760
Shellsort 5,840 0 11,928 6,088
merge sort with cutoff 4,794 0 12,221 4,920

Several things in that table are worth more than a glance.

Insertion sort records zero swaps. It is not standing still: it moves a great deal of data — 63,074 writes — but it does so by shifting elements one position with get and set rather than by exchanging pairs. The swap counter is measuring a particular way of moving data, not movement in general, and an algorithm that avoids the primitive shows up as zero.

That is a real limitation of the count and it is worth stating rather than papering over. To compare data movement across algorithms that move data differently, the honest column is writes, not swaps. By that column insertion sort at 63,074 is one of the heaviest movers here, and selection sort at 1,008 is by far the lightest.

Selection sort’s write count is the whole point of the algorithm. n−1n - 1 swaps at most, so at most 2(n−1)2(n-1) writes, regardless of the input. Nothing else here comes close. Selection sort is the algorithm for the case where writes are catastrophically expensive and reads are cheap — sorting records on media where a write costs orders of magnitude more than a read, which is not the situation most people are in but is exactly the situation the algorithm was designed for.

Merge sort’s reads exceed its writes by nearly three to one. 12,536 against 4,608. Each merge reads both halves and writes the result once, but the comparison primitive charges two reads per comparison, and the copy back from the buffer costs a read and a write each. The asymmetry is structural rather than incidental.

Which count is the right one

There is no answer to that in general, which is the useful thing to know. There is an answer for each situation, and it comes from what the elements are.

Machine integers, in memory. Comparisons and writes cost about the same — a few cycles each — and both are dominated by whether the data is in cache. Here the comparison count is a reasonable proxy for total work and the ranking it gives is roughly right. This is the case most textbooks silently assume.

Large records moved by value. A comparison touches one field; a write moves the whole record. If a record is 200 bytes and a key is 4, a write is fifty times a comparison and the write column is the one that matters. Selection sort’s 1,008 writes at n = 512 start to look extremely attractive against insertion sort’s 63,074, despite selection sort making twice as many comparisons.

Expensive comparisons. Sorting strings by a locale-aware collation, or sorting objects by a computed key, or sorting anything where the comparison is a function call into user code. Now a comparison may cost hundreds of times a write, and the comparison column is not merely a proxy — it is the answer, and everything else is noise. This is why the standard library sorts of most languages work hard to minimise comparisons specifically, and why the information-theoretic floor on comparisons is a bound anyone in this situation genuinely cares about.

Data on disk or across a network. None of these counts is the right one. What matters is the number of blocks transferred, which is a different quantity again, and which the cache model is a small-scale analogue of.

The pattern is that the choice of cost model determines the answer, the choice is a modelling decision rather than a measurement, and it is almost always made implicitly. A benchmark that reports “algorithm A is better” has chosen a cost model — usually by choosing what to sort — and the choice is rarely stated.

Selection sort on four kinds of inputThe same algorithm, the same range of n, four input distributions. The lines nearly coincide — 1.00× between the best and worst input at n = 2048 — so this algorithm's cost barely depends on what it is given, which is a real property and an unusual one.10010³10³10⁴10⁵10⁶ncomparisonsrandomalready sortedreversednearly sortedthe same number of comparisons whatever the input — it never noticescomparisons, counted exactly
Fig. 2 Selection sort on four inputs. The four lines coincide exactly, because the algorithm’s two loops run to completion whatever they find: it performs n(n−1)/2 comparisons on every input of size n. That is an unusual and genuinely useful property — the cost is perfectly predictable — and it is invisible in a classification that says only “quadratic”.

The counts rank differently, and it is not a small effect

Take the eight algorithms in the table and rank them by each count.

By comparisons, best to worst: merge with cutoff, merge, quicksort, Shellsort, heapsort, insertion, bubble, selection.

By writes, best to worst: selection, merge, quicksort, merge with cutoff, Shellsort, heapsort, insertion, bubble.

Selection sort goes from last place to first. That is not a marginal reordering caused by measurement noise — it is a move across the entire field, produced by changing which exact, deterministic, reproducible number is being looked at.

The same effect appears within a single algorithm’s design decisions. Merge sort with an insertion cutoff performs 4,794 comparisons where plain merge sort performs 3,964: the hybrid does 21% more comparing. It also does 6.8% more writing. On this measure the cutoff is a straightforward loss, and yet every production sorting routine implements one, for reasons that turn out to have nothing to do with either count.

A case where the counts disagree about which algorithm is broken

The clearest demonstration is an input that most comparisons never use: an array with only a handful of distinct values. Sorting a million records by a status field with eight possible values is an entirely ordinary thing to want to do, and it is where several respectable algorithms come apart.

At n = 512 with eight distinct values, the comparison counts are:

algorithm random input few distinct values
insertion sort 63,071 55,019
merge sort 3,964 3,837
quicksort, median of three 5,049 19,718
quicksort, random pivot 4,921 17,855
quicksort, first element 4,887 17,990
Shellsort 5,840 3,980

Merge sort barely notices. Shellsort gets slightly faster. Every quicksort variant on the site gets roughly four times slower, and the fitted class moves from nlog⁡nn \log n to n2n^2 — which the site’s machinery detects and refuses to paper over, so none of these algorithms carries a declared class on this input.

The reason is that a two-way partition around a pivot equal to many other elements puts all those equal elements on one side. The recursion is unbalanced not because the pivot was unlucky but because the data has few distinct values, and choosing the pivot better — median of three, at random, any of it — does not help at all. Randomising the pivot defends against an adversarial arrangement of the input, and few-distinct-values is not an arrangement. It is a property of the values themselves, and no pivot rule can escape it.

The fix is a three-way partition, which puts elements equal to the pivot in a middle band and recurses on neither side of it. That is what production quicksorts do, and it costs comparisons on ordinary input to buy safety on this one — a trade that is invisible to anyone who only ever measures random arrays.

Comparison counts against n, few distinct values inputMeasured counts on logarithmic axes, where a power law is a straight line and its exponent is the slope. The quadratic algorithms rise at twice the gradient of the linearithmic ones, and the vertical gaps between the parallel lines are the constants the notation discards.10010³10010³10⁴10⁵10⁶ncomparisonsQuicksortMergeShellsorta power law is a straight line herecomparisons, counted exactly
Fig. 3 Three algorithms on arrays with eight distinct values. Merge sort and Shellsort behave exactly as they do on random data. Median-of-three quicksort’s line bends upward and away — it is measuring as quadratic, and no amount of care in choosing the pivot changes that, because the problem is in the data rather than in the choice.
One partition, with its invariant checked at every stepA Lomuto partition of 16 elements around the pivot 20. Only the steps that moved something are drawn. The invariant — everything left of i is at most the pivot, everything from i+1 to j exceeds it — is checked at every intermediate step by the generator, and the figure does not build if it is ever violated. The pivot finishes at index 6.pivot = 20start74621351061512835363311113820j = 074621351061512835363311113820j = 471021354661512835363311113820j = 1071033546615128353621311113820j = 1271031146615128353621313513820j = 1371031113615128353621313546820j = 1471031113851283536213135466120final swap71031113820283536213135466151green: settled ≤ pivot · orange: under test · purple: the pivotinvariant checked at every step
Fig. 4 Where a quicksort’s counts come from, at a size small enough to read. Each row is one step of a Lomuto partition; the moves are the swaps and the comparisons are what decided them. A single partition of sixteen elements makes fifteen comparisons and a variable number of swaps, and the ratio between those two numbers is entirely a property of the input.

What none of these counts can see

Ordered by how much of the truth they capture, the counts form a ladder — and the top rung is not on it.

Comparisons capture the information-theoretic work. Writes capture the data movement. Reads capture the total traffic. And all three are blind to where the accesses go, which on real hardware is most of the cost.

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. 5 Merge sort and heapsort, every array access from one run, plotted as index against time. Merge sort’s accesses sweep; heapsort’s scatter. Every count in this essay’s table is blind to this difference, and on a real machine it is the difference that decides which one finishes first.

Merge sort and heapsort are both Θ(nlog⁡n)\Theta(n \log n). Merge sort does about half the comparisons. But the interesting number is neither: it is that merge sort makes 49% of its accesses to the next element or the same one, and heapsort makes 14%. Heapsort’s whole method is jumping between a node and its children at indices 2i+12i+1 and 2i+22i+2, which for large heaps are nowhere near each other in memory, and no amount of counting comparisons reveals that.

This is why the site carries a fifth quantity that is not in the table above — the complete access trace, which becomes a modelled miss count when replayed through a cache. That count is genuinely independent of the four here, and the site asserts that it is: if the miss count ever became predictable from the comparison count, the second quantity would be carrying no information and the assertion would fail the build.

Two properties that no count sees at all

Two further things distinguish sorting algorithms and neither is a number.

Stability. A stable sort preserves the relative order of elements that compare equal. Merge sort as written here is stable; heapsort and quicksort are not. Stability decides whether sorting by one key and then by another gives a sensible result, which is how most multi-key sorting is done in practice. It costs nothing in comparisons and is invisible in every column above.

Auxiliary space. Merge sort needs a buffer the size of the input. Heapsort, insertion sort, selection sort and quicksort’s partition need a constant amount. That is a factor-of-n difference in memory, it appears in none of the four counts, and it is frequently the constraint that decides the choice. The site does not currently measure it, which is an honest gap: an in-place sort and an out-of-place one with identical counts are different algorithms and nothing here says so.

Both belong on the list of reasons that “which sorting algorithm is best” is not a question with a number for an answer.

Same class, different constantsEvery algorithm here fits n log n on random input. The bar is the fitted constant — comparisons divided by n log n — and the largest is 1.9 times the smallest. That factor is invisible in the notation and is the whole of what distinguishes these algorithms by this measure.comparisons ÷ n log nMerge sort0.855Merge sort with a cutoff0.992Quicksort, random pivot1.018Quicksort, first-element1.082Quicksort, median of three1.117Shellsort1.246Heapsort1.649all of these fit n log n1.9× between best and worst
Fig. 6 Within the linearithmic class, the fitted comparison constants. Every algorithm here is Θ(n log n) and the spread between best and worst is about two. This is one count, one input kind, and one cost model — change any of the three and the order changes.

What a good comparison looks like

If the counts disagree and there is no universally right one, comparisons between algorithms are not impossible. They just have to say what they are about.

A defensible statement looks like: merge sort performs 0.838 · n log₂ n comparisons on random input, against heapsort’s 1.613 — measured from n = 32 to n = 4,096, averaged over sixteen seeds. Every part of that is checkable, the cost model is named, the range is named, and the sample is named.

An indefensible statement looks like: merge sort is faster than heapsort. It might be true on some data on some machine, and nothing in it says which, so there is no way to find out whether it holds anywhere else.

This site tries to make only the first kind of statement. Where an essay says one algorithm does less work than another, the work is named. Where it says one is faster, something has been measured that entitles it to the word — and given that nothing here is timed, that word is used very sparingly indeed.

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. 7 The extreme version of the same point, from the other end. Five access patterns, each performing exactly 4,096 array accesses — an identical count by any operation-counting analysis — and modelled miss counts differing by a factor of eight. When the count is fixed and the answer still varies by eight, the count was not the whole answer.

The one thing that survives all of it

Amid all this relativity there is a fixed point, and it is worth ending on because it is the reason the comparison count keeps its privileged position despite everything above.

The comparison count is the only one of the four with a proved floor. No comparison sort averages fewer than log⁡2(n!)\log_2(n!) comparisons, ever, for any input distribution, by any technique anyone will ever invent. There is no corresponding theorem about writes, or reads, or swaps: an algorithm that performs zero writes is conceivable if it is allowed to return a permutation rather than rearrange the array, and the write count therefore has no interesting lower bound at all.

So the comparison count is not merely one arbitrary choice among four. It is the count that connects to a theorem, and that is why measuring how close each algorithm gets to its floor is a more informative exercise than measuring the others. It is still not the running time, and it is still not the right count for every situation — but it is the one where the question “could anything do better?” has an answer.

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. 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. 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 Where insertion sort actually wins Every production sorting routine falls back to insertion sort on small subarrays, and the usual explanation is that below some threshold it does fewer comparisons. Measured, it does not — not at sixteen elements, not at eight, not at four. The crossover is real and it is entirely in memory traffic, which is a distinction the usual telling loses.