No figure on this site is a drawing that was made once and saved. Each one is a function:
it takes parameters and returns SVG, so the same generator produces the p4 plate and the
p6m plate without either being redrawn.
That is the reason the collection can keep growing without the illustrations drifting apart.
A generator is written once, checked once, and every essay that calls it inherits the same
line weights, the same colour roles, and the same behaviour in dark mode. There are
25 of them so far.
access-patternWhere each algorithm looks, and when Every 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 sort 49% sequential · 7,540 accesses 256 0 Heapsort 15% sequential · 14,044 accesses 256 0 time (accesses, left to right) · index (bottom to top) one run each, n = 256 every access plotted
amortised-sawtoothThe cost of each of 512 appends One spike per append, on a logarithmic vertical axis. Almost every append costs one unit. 9 of them cost the entire current size, because the array had to be copied, and the largest cost 257 — more than half of all the appends put together would suggest. The mean over the whole sequence is 2.00, which is the amortised cost, and it is a true statement about the sequence and a false one about any append in it. 1 10 100 257 amortised 2.00 0 256 512 append number cost of that append (log scale) growth factor 2, cost = 1 write + a copy of the array when it resizes 9 resizes in 512 appends
asymptotic-error
average-converges
complexity-auditEvery sort measured on random input, and its claim tested The exponent fitted to each algorithm's comparison count across n from 32 to 4096, beside the class it claims. The two groups separate cleanly — nothing measures between 1.3 and 1.9 — and every claim on this input is the class that actually fits. The fitted exponent for a linearithmic algorithm sits near 1.2 rather than 1.0 because n log n is not a power law. fitted exponent of the comparison count 1.0 1.5 2.0 Merge sort with a cutoff 1.16 n log n Quicksort, median of three 1.19 n log n Quicksort, first-element 1.21 n log n Merge sort 1.21 n log n Heapsort 1.22 n log n Quicksort, random pivot 1.24 n log n Shellsort 1.25 n log n Insertion sort 2.00 n^2 Selection sort 2.01 n^2 Bubble sort 2.01 n^2 n from 32 to 4096 comparisons, counted exactly · random input
constant-compareSame class, different constants Every 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 n Merge sort 0.855 Merge sort with a cutoff 0.992 Quicksort, random pivot 1.018 Quicksort, first-element 1.082 Quicksort, median of three 1.117 Shellsort 1.246 Heapsort 1.649 all of these fit n log n 1.9× between best and worst
crossover
decision-treeWhy the floor is log₂(n!): four elements need five comparisons Each internal node is one comparison and has two outcomes, so a run of the algorithm is a root-to-leaf path and the path's length is that run's comparison count. Every one of the 24 orderings of 4 elements must arrive at its own leaf, or two inputs needing different answers would receive the same one. The deepest tree on the left has 16 leaves. Eight orderings, in red, have nowhere to go — so no comparison sort of four elements can always finish in four comparisons, and the floor is ⌈log₂ 24⌉ = 5. every algorithm that makes at most 4 comparisons the 24 orderings of 4 elements root 16 leaves 16 seated · 8 with no leaf one comparison per level, two outcomes per comparison ⌈log₂(4!)⌉ = 5 comparisons
distance-to-floorComparisons used, as a multiple of the floor, n = 256 The information-theoretic floor at n = 256 is 1,684 comparisons: a binary decision tree with 256! leaves cannot be shallower than that. The bar is what each algorithm averaged over 16 random inputs, divided by the floor. Merge sort comes within 2% of it; Selection sort uses 19 times as many. the floor Merge sort 1.02× Quicksort, first 1.23× Quicksort, random 1.24× Merge sort + cutoff 1.29× Quicksort, median-3 1.32× Shellsort 1.45× Heapsort 1.96× Insertion sort 9.69× Bubble sort 19.26× Selection sort 19.38× floor = log₂(256!) = 1,684 comparisons mean of 16 runs, against a proved bound
floor-curve
floor-movesTwo questions, two floors, n = 4096 Sorting 4096 elements cannot be done in fewer than 43,250 comparisons; finding one element in a sorted array of 4096 cannot be done in fewer than 13, and binary search's worst case over all 4096 targets is exactly 13. The difference is a factor of 3,327, and it comes entirely from how many outcomes the algorithm must be able to distinguish — 4096! orderings against 4096 + 1 positions. A lower bound is a property of the question, not of any algorithm. comparisons (bar length is log-scaled) sorting, floor 43,250 sorting, merge sort 43,976 searching, floor 13 searching, binary 13 searching, linear 4,096 green outline: a proved floor · blue: a measured run 3,327× between the two floors
growth-curve
growth-tradeoff
order-matters4,096 accesses, five orders Every 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 misses straight through 512 100% sequential backwards 512 0% sequential every 8th element 4,096 0% sequential every 97th element 4,096 0% sequential uniformly random 3,846 0% sequential fully associative · 32 lines × 8 elements · LRU 8× between best and worst order
partition-stepOne partition, with its invariant checked at every step A 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 = 20 start 7 46 21 35 10 61 51 28 35 36 3 31 11 13 8 20 j = 0 7 46 21 35 10 61 51 28 35 36 3 31 11 13 8 20 j = 4 7 10 21 35 46 61 51 28 35 36 3 31 11 13 8 20 j = 10 7 10 3 35 46 61 51 28 35 36 21 31 11 13 8 20 j = 12 7 10 3 11 46 61 51 28 35 36 21 31 35 13 8 20 j = 13 7 10 3 11 13 61 51 28 35 36 21 31 35 46 8 20 j = 14 7 10 3 11 13 8 51 28 35 36 21 31 35 46 61 20 final swap 7 10 3 11 13 8 20 28 35 36 21 31 35 46 61 51 green: settled ≤ pivot · orange: under test · purple: the pivot invariant checked at every step
pivot-rules
probe-count
quicksort-spread600 runs of quicksort, random pivot at n = 512 Every bar is the number of independent random inputs that cost that many comparisons. The mean is 4945; the median is 4908; the worst of 600 runs cost 6,543, which is 1.32 times the mean. The distribution is tight — a relative standard deviation of 6.8% — and skewed to the right, which is the shape that makes "on average" a defensible thing to say about this algorithm and a misleading thing to say about the version that takes the first element as its pivot. mean 4945 99th 6030 4,282 5,413 6,543 comparisons runs 600 independent random inputs, n = 512 worst run 1.32× the mean
sort-traceInsertion sort on 24 random elements, six moments from one run Each panel is the array as it actually stood after a particular write, sampled evenly across the 159 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 157 comparisons and 0 swaps. after 0 writes 0 cmp after 32 writes 32 cmp after 64 writes 63 cmp after 95 writes 94 cmp after 127 writes 125 cmp after 159 writes 157 cmp random input, seed stated in lib/count.js 157 comparisons in this run
tail-growth
tree-shapeThe same 63 keys, inserted in two orders Both trees hold the keys 0 to 62. On the left they arrived in order, and the tree has height 62 — every node has one child, and a lookup costs a linear scan. On the right the same keys arrived shuffled, giving height 10 against an ideal of 5. Both figures are truncated at depth 16 because the left one does not fit. The logarithmic lookup a binary search tree is chosen for is a property of the insertion order, not of the structure. sorted insertion — height 62 shuffled insertion — height 10 truncated at depth 16 63 keys, identical set, different arrival order 62 deep against 10
two-countsComparisons and swaps at n = 512 Selection 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. comparisons swaps Insertion sort 63,071 / 0 Selection sort 130,816 / 504 Bubble sort 129,688 / 62,563 Merge sort 3,964 / 0 Heapsort 7,653 / 4,170 Quicksort 5,049 / 2,380 n = 512, random input counted in the same run
two-quantitiesComparisons against modelled cache misses, n = 2048 One 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⁵ comparisons cache misses (modelled) Insertion sort Selection sort Bubble sort Merge sort Heapsort Quicksort, first Quicksort, median-3 Quicksort, random Shellsort Merge + cutoff fully associative · 64 lines × 8 elements · LRU a modelled count, not a time
working-set