{"id": "card_cs_sorting_algorithms", "kind": "reference", "title": "Sorting algorithms — the roll of eighty-six and the bound none can beat", "body": "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.", "source": {"label": "Narrow Highway — computer science", "url": "", "authority_tier": "engine_derived", "ref": "stick_sorting_algorithms_the_roll_and_the_bound_none_can_beat"}, "shelf": "codex", "box": "computer_science", "bands": ["sorting", "sorting algorithm", "sorting algorithms", "sort", "quicksort", "merge sort", "mergesort", "heapsort", "insertion sort", "bubble sort", "shellsort", "timsort", "powersort", "radix sort", "counting sort", "bucket sort", "sorting network", "batcher", "bitonic", "comparison sort", "lower bound", "n log n", "stable sort", "topological sort", "bogosort", "pancake sort", "knuth", "algorithm", "computer science", "one map"], "subject": "Sorting algorithms — the roll of eighty-six and the bound none can beat", "connections": [{"to_card_id": "card_floor_computer_science", "relationship": "part_of", "evidence": "sorting is the algorithms pillar at depth: the roll of eighty-six and the log2 n! bound"}, {"to_card_id": "card_cs_algorithms", "relationship": "connects_at", "evidence": "the pillar seals merge sort's 24 at eight items; the roll seals the exact worst case, 17, and the floor, 16"}, {"to_card_id": "card_floor_logarithm", "relationship": "connects_at", "evidence": "log2 n! prices the comparison bound; the base of the logarithm sits in the stooge exponent log 3 / log 1.5"}, {"to_card_id": "card_tool_reservoir_computing", "relationship": "connects_at", "evidence": "the trained readout is a weighted sum and then a sort: top-k by score is a partial sort (a heap)"}, {"to_card_id": "card_cs_logic_gates", "relationship": "connects_at", "evidence": "a comparison is one Boolean decision; the three-way comparison (<, =, >) is the third value, -1 0 1"}, {"to_card_id": "card_src_word_sorting_algorithm", "relationship": "connects_at", "evidence": "the dictionary's own definition: an algorithm for sorting a list (WordNet)"}], "author": "engine", "created_at": 0.0, "updated_at": 0.0, "visibility": "public", "lifecycle_stage": "public", "volatility": "permanent", "surface": "secular", "generated": false, "call": "codex.computer.science", "facets": {"subject": ["algorithm", "batcher", "bitonic", "bogosort", "bubble sort", "bucket sort", "comparison sort", "computer science", "counting sort", "heapsort", "insertion sort", "knuth", "lower bound", "merge sort", "mergesort", "n log n", "one map", "pancake sort", "powersort", "quicksort", "radix sort", "shellsort", "sort", "sorting", "sorting algorithm", "sorting algorithms", "sorting network", "stable sort", "timsort", "topological sort"]}, "presentation": {"glyph": "•", "kind_label": "computer science", "by": "Narrow Highway — computer science", "authority": "engine_derived", "posted": "", "standing": ""}, "neighbors": [{"id": "card_floor_computer_science", "title": "Computer science — bits, logic, and what can be computed", "relationship": "part of", "why": "sorting is the algorithms pillar at depth: the roll of eighty-six and the log2 n! bound", "href": "/card/card_floor_computer_science", "resolved": true}, {"id": "card_cs_algorithms", "title": "Algorithms — good beats bad", "relationship": "connects at", "why": "the pillar seals merge sort's 24 at eight items; the roll seals the exact worst case, 17, and the floor, 16", "href": "/card/card_cs_algorithms", "resolved": true}, {"id": "card_floor_logarithm", "title": "The logarithm - the instrument the joints share", "relationship": "connects at", "why": "log2 n! prices the comparison bound; the base of the logarithm sits in the stooge exponent log 3 / log 1.5", "href": "/card/card_floor_logarithm", "resolved": true}, {"id": "card_tool_reservoir_computing", "title": "Reservoir computing — a fixed substrate, a trained readout; our use of it", "relationship": "connects at", "why": "the trained readout is a weighted sum and then a sort: top-k by score is a partial sort (a heap)", "href": "/card/card_tool_reservoir_computing", "resolved": true}, {"id": "card_cs_logic_gates", "title": "Logic gates — the 16 functions of two inputs", "relationship": "connects at", "why": "a comparison is one Boolean decision; the three-way comparison (<, =, >) is the third value, -1 0 1", "href": "/card/card_cs_logic_gates", "resolved": true}, {"id": "card_src_word_sorting_algorithm", "title": "sorting algorithm", "relationship": "connects at", "why": "the dictionary's own definition: an algorithm for sorting a list (WordNet)", "href": "/card/card_src_word_sorting_algorithm", "resolved": true}], "house": {"door": "FIND", "kind": "card", "trail": "connections", "seal": "/card/card_cs_sorting_algorithms", "next_step": {"do": "follow a connection: what this card rests on, and what rests on it", "door": "FIND", "tool": "card_connections", "params": {"id": "card_cs_sorting_algorithms"}}, "ends": "a verdict or a card · the trail · a seal · one next step"}}