A card from a free library — ask anything, no account, works offline. Every card carries its source.
Sorting algorithms — the roll of eighty-six and the bound none can beat
computer science
To sort is to find the one order among n! - and a comparison answers one two-valued question, so no comparison sort beats log2 n! comparisons (Knuth, TAOCP vol. 3, 5.3.1). Eight items: 8! = 40,320 orders, a floor of 16 comparisons, and Ford-Johnson's merge insertion (1959) reaches it (sealed on the sorting_algorithms stick; run tick.py sorting_algorithms). The worst cases, sealed at a thousand items: merge sort n lg n - 2^lg n + 1 = 8,977 (within 5 percent of the 8,530 floor); heapsort 2 n lg n = 19,932, in place; insertion n(n-1)/2 = 499,500. Sorting as WIRING: Batcher's odd-even merge network sorts eight wires with 19 comparators in 6 layers, the proven optimum, and the bitonic sorter with 24 (sealed; tools/sorting_demo.py builds both and proves them on all 256 zero-one inputs by Knuth's zero-one principle). Shellsort's Knuth gaps reach 1093 (sealed); the stooge exponent is log 3 / log 1.5 = 2.71 (sealed) - recursion is not speed; timsort's minrun for a thousand is 63 (sealed) and every list.sort in this engine is timsort with the powersort merge policy; pancake sort needs at most 18n/11 flips (sealed); bogosort expects (n-1) n! = 282,240 swaps for eight (sealed) - the roll keeps both ends. EIGHTY-SIX named algorithms in seven families, each with its origin cited: exchange (bubble, comb, gnome, quicksort and its three-way, dual-pivot, intro and pdq forms, radix exchange, stooge, slowsort), selection (heapsort, smoothsort, weak-heap, Cartesian tree, tournament, cycle), insertion (binary, shellsort, library, patience, tree, splay, Ford-Johnson, address calculation), merge (von Neumann's, natural, timsort, powersort, block, grail, quad/flux/crum, glide, polyphase, cascade, oscillating), distribution (counting, bucket, LSD and MSD radix back to Hollerith's 1890 census machines, American flag, multikey quicksort, burstsort, flashsort, spreadsort), networks and parallel (Batcher, pairwise, Green's sixteen, shear, samplesort, PSRS, merge path, GPU radix, cubesort) and the analog, pessimal and key-less end (bead, spaghetti, pancake, Franceschini, bogo, sleep, Kahn's and Tarjan's topological sorts). OUR USE: the engine sorts 362 times in 124 modules (2026-10-31); it relies on STABILITY by name (equal keys keep the order they were found in - provenance preserved), ranks by a total order with a deterministic tie-break, walks the priced map with a heap, merges sorted shards, and names its search cache RADIX against the COMPARISON rung; the ledger's sort of every file per append is the open want. Rests on the computer-science floor and its algorithms pillar, the logarithm, the reservoir (the readout is a weighted sum, then a sort), Boole's gates (the three-way comparison is the third value) and the dictionary's word.
- part of → Computer science — bits, logic, and what can be computed — sorting is the algorithms pillar at depth: the roll of eighty-six and the log2 n! bound
- connects at → Algorithms — good beats bad — the pillar seals merge sort's 24 at eight items; the roll seals the exact worst case, 17,
- connects at → The logarithm - the instrument the joints share — log2 n! prices the comparison bound; the base of the logarithm sits in the stooge exponent
- connects at → Reservoir computing — a fixed substrate, a trained readout; our use of it — the trained readout is a weighted sum and then a sort: top-k by score is a partial sort (a
- connects at → Logic gates — the 16 functions of two inputs — a comparison is one Boolean decision; the three-way comparison (<, =, >) is the third valu
- connects at → sorting algorithm — the dictionary's own definition: an algorithm for sorting a list (WordNet)
Is this card incomplete? Tell the library — it will call out for more ↗