{ "model": { "rank": 6531, "code": "thing-q181593", "model_id": "vr.tr.sorting-algorithm", "name": "sorting algorithm", "purpose": "Enable an AI agent to recognise a sorting algorithm, assess its ordering guarantees and resource demands, and decide whether and how it may be used for a particular sorting task.", "family": "Thing Registry", "category": "Information and virtual systems", "status": "research-draft", "kind": "thing", "plane": "INF", "domain": "INF.MED", "industry": "", "version": "", "url": "/models/thing/q181593/", "tier": 2, "score": 60, "payload": { "layer": "wikidata", "aliases": [ "quantum sort", "topological sorting algorithm", "flashsort", "Manchester_triage", "merge sort", "Canadian Triage and Acuity Scale", "external sorting", "Stupid sort", "JumpSTART triage", "comparison sort", "stable sorting algorithm", "adaptive sort", "quicksort", "Computer-aided simple triage", "ecological triage", "sorting network", "Simple triage and rapid treatment", "shellsort", "pairwise sorting network" ], "aliasCount": 19, "merged": 19, "knownIn": 60, "facets": null, "markers": [], "lexicalClass": "", "senseRank": null, "alsoRegisteredAs": null, "source": { "dataset": "wikidata", "item": "Q181593", "url": "https://www.wikidata.org/wiki/Q181593", "license": "CC0 1.0" } }, "research": { "vercy": "1.0-draft", "publication": { "status": "research-draft", "adjudicationStatus": "unreviewed", "publishableCanonical": false, "generatedAt": "2026-09-07T15:10:12Z", "providers": [ "Codex", "Grok" ], "missingProviders": [], "pass": 2, "cost": { "grok": { "usd": 0.01083852, "turns": 1, "seconds": 114, "error": null }, "codex": { "seconds": 72.2, "error": "Reading additional input from stdin...\nOpenAI Codex v0.153.3\n--------\nworkdir: R:\\02_PROJECTS\\02_Meta_Models_Platforms\\Ver.cy\\current\\thing-registry-backlog\nmodel: gpt-6-astra\nprovider: openai\napproval: never\nsandbox: read-only\nreasoning effort: none\nreasoning summaries: none\nsession id: 01a07c67-d779-73d0-b595-013263045159\n--------\nuser\nYou are drafting a Vercy meta-model for one registered thing. Answer as JSON only, no prose around it.\n\nThing: sorting algorithm\nRegistry id: vr.tr.sorting-algorithm\nPlane / domain: INF / INF.MED\nRegistry definition: (none recorded)\nNames folded into this entr" } } }, "metaModel": { "id": "THING-Q181593", "registryId": "vr.tr.sorting-algorithm", "name": "sorting algorithm", "version": "0.1.0-research.1", "entryKind": "thing", "family": "Thing Registry", "domain": [ "INF.MED" ], "status": "research-draft" }, "canonicalUrl": "https://ver.cy/models/thing/q181593/", "model": { "registry_id": "vr.tr.sorting-algorithm", "name": "sorting algorithm", "purpose": "Enable an AI agent to recognise a sorting algorithm, assess its ordering guarantees and resource demands, and decide whether and how it may be used for a particular sorting task.", "definition": "A sorting algorithm is a finite procedure that permutes a finite sequence of records so their keys appear in a prescribed total order, using pairwise comparison or digit/radix (distribution) extraction, optionally with extra guarantees such as stability, in-place working storage, or a worst-case time bound.", "scope_statement": "This model owns the identity, ordering contract, computational method, correctness conditions, resource behaviour and applicability of a sorting algorithm, while distinguishing algorithmic guarantees from properties of particular implementations and runs.", "in_scope": [ "The ordering problem solved, including permitted inputs and required output relationships.", "The computational method and variants that materially change sorting guarantees.", "Correctness, termination, stability and preservation of input elements.", "Time, auxiliary storage and data movement under stated assumptions.", "Requirements and limitations governing selection, execution and adaptation." ], "out_of_scope": [ "Dataset contents, ownership, quality and lifecycle.", "Business definitions of ranking criteria and domain-specific comparison policies.", "Source-code packaging, dependencies and implementation release management.", "Hardware, storage systems and distributed execution infrastructure.", "Individual execution logs and benchmark experiment records.", "Selection, searching, grouping and indexing methods that do not themselves produce a sorted sequence." ], "distinguishing_features": [ "Its successful result orders all elements in the declared input scope; returning only a minimum, a rank or a top-k subset is insufficient.", "Its output preserves the input elements and their multiplicities, or supplies a permutation referencing them; filtering and deduplication change the task.", "It specifies a computational procedure for producing the order; a comparator or sorting criterion alone is not a sorting algorithm.", "It establishes order for a supplied collection; maintaining a searchable ordered data structure is a neighbouring responsibility unless a sorting procedure is explicitly identified.", "It declares the relationship between its ordering assumptions and output guarantee, allowing comparison-based, key-based and other sorting methods to be distinguished." ], "characteristics": [ { "name": "Ordering mechanism", "kind": "category", "unit_or_values": "Comparison-based, key-distribution-based, hybrid, or another explicitly described mechanism.", "why_it_matters": "Determines which input assumptions and operations support the sorting guarantee." }, { "name": "Required ordering relation", "kind": "relation", "unit_or_values": "Reference to the comparator, key order or relation, with its required mathematical properties.", "why_it_matters": "An incompatible or inconsistent ordering relation can invalidate correctness or termination claims." }, { "name": "Stability guarantee", "kind": "category", "unit_or_values": "Guaranteed, conditional, not guaranteed, or unresolved; conditions stated explicitly.", "why_it_matters": "Determines whether elements equivalent under the sorting criterion retain their relative input order." }, { "name": "Time growth", "kind": "measurement", "unit_or_values": "Asymptotic bounds by best, worst, average or expected case, with cost model and parameters such as element count, key width and key range.", "why_it_matters": "Supports workload selection without conflating distinct assumptions or forms of guarantee." }, { "name": "Auxiliary storage growth", "kind": "measurement", "unit_or_values": "Asymptotic storage bound, explicitly accounting for recursion, buffers and output representation.", "why_it_matters": "Determines feasibility under memory constraints and clarifies any in-place claim." }, { "name": "Input adaptivity", "kind": "relation", "unit_or_values": "Resource behaviour relative to specified input properties, such as runs, inversions, duplicate frequency or key distribution.", "why_it_matters": "Reveals whether existing structure improves performance or creates a pathological case." }, { "name": "Access and mutation requirements", "kind": "category", "unit_or_values": "Required access operations, permitted mutation, element movement constraints and output form.", "why_it_matters": "Determines compatibility with arrays, linked sequences, external storage and protected inputs." }, { "name": "Use readiness", "kind": "state", "unit_or_values": "Unassessed, applicable under recorded conditions, requires adaptation, unsuitable, or unresolved for a specified task.", "why_it_matters": "Connects the algorithm's recorded properties to an actionable assessment of a concrete sorting need." } ], "affordances": [ "Check whether a proposed comparator, key domain and input representation satisfy the algorithm's preconditions.", "Select or reject the algorithm against stability, latency, memory and access constraints.", "Identify a variant or parameterisation and reassess any guarantees it changes.", "Derive correctness checks and adversarial test cases from the ordering contract.", "Estimate resource requirements using a stated workload and cost model.", "Determine whether an implementation or execution result conforms to the recorded algorithm and guarantees." ] }, "sources": [ { "id": "knuth-taocp-3", "title": "The Art of Computer Programming, Volume 3: Sorting and Searching", "url": "", "what_it_supports": "Canonical analysis of comparison and distribution methods, external sorting, and the information-theoretic n log n lower bound." }, { "id": "clrs", "title": "Introduction to Algorithms", "url": "", "what_it_supports": "Standard textbook treatment of heapsort, quicksort, mergesort, counting/radix/bucket sorts, and decision-tree lower bounds (Cormen, Leiserson, Rivest, Stein; MIT Press)." }, { "id": "iso-14882", "title": "ISO/IEC 14882 Programming languages - C++", "url": "", "what_it_supports": "Normative contracts for std::sort and std::stable_sort, including complexity and the requirement that the comparator induce a strict weak ordering." }, { "id": "iso-9899", "title": "ISO/IEC 9899 Programming languages - C", "url": "", "what_it_supports": "The qsort library specification used as the classic portable C sorting interface." }, { "id": "uts-10", "title": "Unicode Technical Standard #10: Unicode Collation Algorithm", "url": "https://www.unicode.org/reports/tr10/", "what_it_supports": "Defines the total order on strings that a sort consumes; explains why locale and collation, not the rearrangement procedure, drive regional key order.", "url_status": "live" }, { "id": "python-sorting-howto", "title": "Sorting HOW TO", "url": "https://docs.python.org/3/howto/sorting.html", "what_it_supports": "Documents a widely deployed stable adaptive sort (Timsort) and the distinction between key functions and rich comparisons.", "url_status": "live" }, { "id": "wikipedia-sorting-algorithm", "title": "Sorting algorithm", "url": "https://en.wikipedia.org/wiki/Sorting_algorithm", "what_it_supports": "Survey of families, stability, memory, and named algorithms as commonly distinguished in practice.", "url_status": "live" } ], "structure": { "bundles": [ { "id": "sorting-contract", "name": "Sorting contract", "description": "The exact input-to-output obligation that makes the procedure a sorting algorithm.", "rationale": "An agent needs a precise success condition before judging correctness or selecting a method.", "layers": [ { "id": "input-and-order", "name": "Input and order", "description": "The sortable collection, key interpretation and ordering assumptions.", "findings": [ { "id": "admissible-ordering", "name": "Admissible ordering", "description": "Record the input scope and the properties required of comparisons or sortable keys.", "questions": [ { "text": "What collection is sorted, which keys or comparisons establish order, and what properties must that order satisfy?", "kind": "definition", "id": "admissible-ordering-q01" }, { "text": "How are equivalent keys, missing values, incomparable values and exceptional numeric values treated or excluded?", "kind": "boundary", "id": "admissible-ordering-q02" } ] } ] }, { "id": "output-obligations", "name": "Output obligations", "description": "The required ordering, element preservation and treatment of equivalent elements.", "findings": [ { "id": "sorted-permutation", "name": "Sorted permutation", "description": "Record how the result demonstrates sortedness while preserving every input occurrence.", "questions": [ { "text": "What postcondition establishes sortedness, and does the result rearrange elements, copy them or return a permutation of references?", "kind": "definition", "id": "sorted-permutation-q01" }, { "text": "How must the result preserve multiplicities and, when stability is required, the relative order of equivalent elements?", "kind": "boundary", "id": "sorted-permutation-q02" } ] } ] } ] }, { "id": "computational-method", "name": "Computational method", "description": "The operations and control structure that identify the algorithm and distinguish its variants.", "rationale": "Names alone do not establish which procedure or guarantees an agent is evaluating.", "layers": [ { "id": "sorting-mechanism", "name": "Sorting mechanism", "description": "How the procedure progressively establishes the required order.", "findings": [ { "id": "ordering-procedure", "name": "Ordering procedure", "description": "Record the defining steps, primitive operations and progress rule.", "questions": [ { "text": "Which steps establish order, such as partitioning, merging, insertion, heap operations or distribution by key digits?", "kind": "definition", "id": "ordering-procedure-q01" }, { "text": "Which readable algorithm description or pseudocode defines those steps and their stopping conditions?", "kind": "provenance", "id": "ordering-procedure-q02" } ] } ] }, { "id": "variants-and-controls", "name": "Variants and controls", "description": "Choices that alter the procedure's identity, behaviour or guarantees.", "findings": [ { "id": "material-variant-choices", "name": "Material variant choices", "description": "Record consequential choices such as pivot rules, radix, merge scheduling and fallback thresholds.", "questions": [ { "text": "Which choices define this variant, including any randomness, hybrid stages or fallback method?", "kind": "definition", "id": "material-variant-choices-q01" }, { "text": "Which guarantees must be reassessed before changing one of those choices?", "kind": "action", "id": "material-variant-choices-q02" } ] } ] } ] }, { "id": "correctness-and-assurance", "name": "Correctness and assurance", "description": "The basis for trusting sortedness, preservation, stability and termination.", "rationale": "An agent must distinguish a claimed guarantee from one supported for the specified procedure and assumptions.", "layers": [ { "id": "proof-obligations", "name": "Proof obligations", "description": "The invariants and progress arguments supporting the sorting contract.", "findings": [ { "id": "guarantee-support", "name": "Guarantee support", "description": "Record evidence for each correctness property and the assumptions on which it depends.", "questions": [ { "text": "What invariants and progress argument establish sortedness, element preservation and termination?", "kind": "definition", "id": "guarantee-support-q01" }, { "text": "Which sources support those guarantees and any stability claim for this exact variant?", "kind": "provenance", "id": "guarantee-support-q02" } ] } ] }, { "id": "conformance-checks", "name": "Conformance checks", "description": "Observable checks linking implementations and outputs to the algorithm's contract.", "findings": [ { "id": "sorting-validation", "name": "Sorting validation", "description": "Record checks capable of detecting ordering, preservation and stability failures.", "questions": [ { "text": "Which checks independently verify output order, input multiplicities and required stability?", "kind": "action", "id": "sorting-validation-q01" }, { "text": "Which boundary inputs exercise this method's failure modes, including empty inputs, equivalent keys and adverse input arrangements?", "kind": "boundary", "id": "sorting-validation-q02" } ] } ] } ] }, { "id": "resource-behaviour", "name": "Resource behaviour", "description": "The algorithm's computational costs and sensitivity to input structure.", "rationale": "Sorting methods with the same output contract can have materially different feasibility and performance.", "layers": [ { "id": "cost-model-and-bounds", "name": "Cost model and bounds", "description": "The operations counted and the conditions governing resource bounds.", "findings": [ { "id": "time-and-space-costs", "name": "Time and space costs", "description": "Record time and auxiliary storage bounds without hiding key processing, recursion or buffering.", "questions": [ { "text": "What time bounds apply by case, under which cost model and parameters, and what distribution or randomness supports average or expected claims?", "kind": "measurement", "id": "time-and-space-costs-q01" }, { "text": "What auxiliary storage is required, and does the accounting include recursion, temporary buffers and output storage?", "kind": "measurement", "id": "time-and-space-costs-q02" } ] } ] }, { "id": "input-sensitive-costs", "name": "Input-sensitive costs", "description": "How input arrangement, key properties and operation costs change performance.", "findings": [ { "id": "adaptivity-and-pathologies", "name": "Adaptivity and pathologies", "description": "Record favourable and adverse workloads and the evidence separating them.", "questions": [ { "text": "How do existing runs, inversions, duplicate keys, key width or key range affect the relevant operation counts?", "kind": "measurement", "id": "adaptivity-and-pathologies-q01" }, { "text": "Which inputs trigger worst-case behaviour, and what evidence supports any proposed mitigation?", "kind": "boundary", "id": "adaptivity-and-pathologies-q02" } ] } ] } ] }, { "id": "application-and-execution-constraints", "name": "Application and execution constraints", "description": "Conditions governing whether the algorithm can serve a particular sorting task.", "rationale": "An agent needs to turn abstract guarantees into a justified decision about use or adaptation.", "layers": [ { "id": "representation-compatibility", "name": "Representation compatibility", "description": "Required input access, movement permissions and execution capabilities.", "findings": [ { "id": "access-and-movement-preconditions", "name": "Access and movement preconditions", "description": "Record the operations the input representation and execution environment must support.", "questions": [ { "text": "Does this procedure require random access, repeated passes, writable storage, movable elements or specific key operations?", "kind": "boundary", "id": "access-and-movement-preconditions-q01" }, { "text": "Which adaptations are required for linked sequences, external storage or parallel execution, and which guarantees would need revalidation?", "kind": "action", "id": "access-and-movement-preconditions-q02" } ] } ] }, { "id": "selection-and-use", "name": "Selection and use", "description": "A task-relative suitability decision grounded in the recorded contract and costs.", "findings": [ { "id": "sorting-task-fit", "name": "Sorting task fit", "description": "Record why the algorithm is usable, unsuitable or insufficiently assessed for a stated workload.", "questions": [ { "text": "Do the task's ordering, stability, mutation, memory and latency requirements fit the guarantees under the anticipated workload?", "kind": "action", "id": "sorting-task-fit-q01" }, { "text": "What additional evidence or adaptation is needed before selecting an implementation and executing it?", "kind": "action", "id": "sorting-task-fit-q02" } ] } ] } ] }, { "id": "evidence-and-external-alignment", "name": "Evidence and external alignment", "description": "What the world already says about this thing, gathered so the model can be checked against it.", "rationale": "A model that cannot be lined up against existing standards, identifiers and practice cannot be adopted by anyone who already uses them.", "layers": [ { "id": "reported-evidence", "name": "Reported evidence", "description": "Findings from the breadth pass, kept separate from the structural claims.", "findings": [ { "id": "evidence-kinds", "name": "Kinds and varieties", "description": "Reported by the breadth pass; each item needs checking against its source before it becomes normative.", "evidence": [ "Comparison-based internal sorts (insertion, quicksort, mergesort, heapsort and their variants)", "Non-comparison distribution sorts (counting sort, radix sort, bucket sort)", "Stable versus unstable sorts (whether equal keys keep their input order)", "In-place versus not-in-place sorts (extra memory beyond a few words)", "Adaptive sorts that exploit existing runs or near-sorted input (Timsort, insertion on nearly ordered data)", "External / out-of-core sorts (k-way merge and related tape/disk algorithms)", "Parallel and distributed sorts (bitonic, sample sort, MapReduce/Spark shuffle-sort)", "Hybrid introspective library sorts (introsort, Timsort, pdqsort)" ], "questions": [ { "id": "evidence-kinds-q01", "text": "Which of these kinds and varieties hold for the sense of sorting algorithm this model covers, and on what evidence?", "kind": "provenance" } ] }, { "id": "evidence-identifiers", "name": "Identifiers and schemes", "description": "Reported by the breadth pass; each item needs checking against its source before it becomes normative.", "evidence": [ { "scheme": "Wikidata", "value_or_pattern": "Q128317", "note": "Item for the class \"sorting algorithm\"; individual named methods have their own items." }, { "scheme": "ACM Computing Classification System (2012)", "value_or_pattern": "Theory of computation → Design and analysis of algorithms → Sorting and searching", "note": "Concept heading, not a numeric instance identifier for a particular algorithm." }, { "scheme": "ISO C library", "value_or_pattern": "qsort", "note": "Identifier of the standard C sorting function in (ISO/IEC 9899)." }, { "scheme": "ISO C++ standard library", "value_or_pattern": "std::sort | std::stable_sort | std::partial_sort", "note": "Canonical C++ algorithm names (ISO/IEC 14882)." } ], "questions": [ { "id": "evidence-identifiers-q01", "text": "Which of these identifiers and schemes hold for the sense of sorting algorithm this model covers, and on what evidence?", "kind": "provenance" } ] }, { "id": "evidence-standards-and-regulation", "name": "Standards and regulation", "description": "Reported by the breadth pass; each item needs checking against its source before it becomes normative.", "evidence": [ "ISO/IEC 9899 (ISO/IEC JTC 1/SC 22) - qsort in the C standard library", "ISO/IEC 14882 (ISO/IEC JTC 1/SC 22) - std::sort / std::stable_sort; comparator must be a strict weak ordering", "IEEE Std 1003.1 / POSIX.1 (IEEE and The Open Group) - qsort", "ECMA-262 (Ecma International); aligned ISO/IEC 22275 - Array.prototype.sort, required to be stable since ECMAScript 2019", "Unicode Technical Standard #10 (Unicode Consortium) - collation (the order relation), not the permutation procedure itself" ], "questions": [ { "id": "evidence-standards-and-regulation-q01", "text": "Which of these standards and regulation hold for the sense of sorting algorithm this model covers, and on what evidence?", "kind": "provenance" } ] }, { "id": "evidence-real-world-use", "name": "Real-world use", "description": "Reported by the breadth pass; each item needs checking against its source before it becomes normative.", "evidence": [ "Database engines implementing SQL ORDER BY and building/maintaining B-tree and LSM indexes", "Spreadsheet and interactive table column sorts in office and web UIs", "The shuffle/sort phase of MapReduce, Spark, and similar distributed dataflow systems", "Construction of inverted-index posting lists in search engines", "Default language-runtime sorts (CPython list.sort, Java Arrays.sort / Collections.sort, C++ std::sort, Rust slice::sort)", "Restoring time order of logs or packets after parallel ingest", "Preprocessing in computational geometry (e.g. Graham scan) and painter's-algorithm depth order" ], "questions": [ { "id": "evidence-real-world-use-q01", "text": "Which of these real-world use hold for the sense of sorting algorithm this model covers, and on what evidence?", "kind": "provenance" } ] }, { "id": "evidence-measurements", "name": "Typical measurements", "description": "Reported by the breadth pass; each item needs checking against its source before it becomes normative.", "evidence": [ { "quantity": "Comparison count (comparison sorts)", "typical_range": "about n log2 n to ~1.4 n log2 n in the average case; Ω(n log n) worst-case lower bound; O(n²) for naive quadratic methods", "unit": "comparisons" }, { "quantity": "Asymptotic time", "typical_range": "O(n log n) typical library default; O(n) for integer/radix sorts under bounded keys; O(n²) worst case without introspective fallback", "unit": "element operations" }, { "quantity": "Extra working memory", "typical_range": "O(1) words (true in-place) through O(log n) (typical quicksort/introsort stack) to O(n) (mergesort, counting/radix auxiliary arrays)", "unit": "machine words or records" }, { "quantity": "Input size encountered in practice", "typical_range": "tens of elements in UI widgets; 10^6-10^9 in-memory; 10^12+ in external/distributed sorts", "unit": "records" }, { "quantity": "Recursion or call-stack depth", "typical_range": "O(log n) with balanced or introspective control; O(n) for naive quicksort on adversarial input", "unit": "frames" } ], "questions": [ { "id": "evidence-measurements-q01", "text": "Which of these typical measurements hold for the sense of sorting algorithm this model covers, and on what evidence?", "kind": "provenance" } ] }, { "id": "evidence-failure-modes-and-hazards", "name": "Failure modes and hazards", "description": "Reported by the breadth pass; each item needs checking against its source before it becomes normative.", "evidence": [ "Comparator or key function that is not a strict weak ordering (intransitive, time-varying, or NaN-breaking trichotomy) causing non-termination, corruption, or undefined behaviour in C++", "Naive quicksort degrading to O(n²) time and O(n) stack, with stack overflow, unless limited by introsort/pdqsort-style fallbacks", "Unstable sort destroying secondary-key order in multi-column or decorate-sort-undecorate workflows", "Integer overflow in midpoint calculations such as (low+high)/2 on large index types", "Locale/collation mismatch: byte order, code-point order, and dictionary/phonebook order disagree on the same strings", "External sort exhausting scratch space or leaving a partial run set after a crash", "Equal-key or floating-point edge cases (−0.0, NaN) producing platform-dependent order", "Rare timing or comparison side channels when the keys or comparator are secret" ], "questions": [ { "id": "evidence-failure-modes-and-hazards-q01", "text": "Which of these failure modes and hazards hold for the sense of sorting algorithm this model covers, and on what evidence?", "kind": "provenance" } ] }, { "id": "evidence-regional-variation", "name": "Regional variation", "description": "Reported by the breadth pass; each item needs checking against its source before it becomes normative.", "evidence": [ "String key order is locale- and collation-dependent (e.g. German phonebook ä≈ae, Swedish å after z, CJK radical/stroke vs pinyin vs Unicode code point), so the same algorithm yields different permutations", "Default library algorithm differs by platform: Timsort in CPython and Java object sorts; dual-pivot quicksort for Java primitives; introsort in libstdc++; pdqsort-style patterns in Rust", "Teaching and trade names differ (French tri/algorithme de tri, German Sortierverfahren) though the named methods are international", "Numeric and date keys inherit local parsing (decimal comma vs point; DMY vs MDY), which changes keys rather than the rearrangement procedure" ], "questions": [ { "id": "evidence-regional-variation-q01", "text": "Which of these regional variation hold for the sense of sorting algorithm this model covers, and on what evidence?", "kind": "provenance" } ] }, { "id": "evidence-neighbours", "name": "Neighbouring kinds and how to tell them apart", "description": "Reported by the breadth pass; each item needs checking against its source before it becomes normative.", "evidence": [ { "name": "Selection / order-statistic algorithm (e.g. quickselect)", "difference": "Returns the k-th ordered element (or partitions around it) without putting every element into final position; a full sort orders all positions." }, { "name": "Collation algorithm (Unicode UCA and locale tailorings)", "difference": "Defines the total order on strings; a sorting algorithm only applies some already-given order to permute records." }, { "name": "Priority queue / binary heap", "difference": "Maintains a partial order so the next extremum can be extracted; it yields a fully sorted sequence only if used as heapsort." }, { "name": "Topological sort", "difference": "Linearises a directed acyclic graph consistently with a partial order on vertices; it does not sort arbitrary totally ordered keys." }, { "name": "Searching algorithm", "difference": "Locates a key in a collection; it does not rearrange the collection into sorted order (though binary search assumes that order already holds)." }, { "name": "Shuffle / random permutation", "difference": "Draws an (often uniform) unordered rearrangement; a sort aims at a specific total order, not mixing." }, { "name": "Hash partitioning / grouping", "difference": "Clusters equal keys or buckets by hash without placing distinct keys into sorted sequence." } ], "questions": [ { "id": "evidence-neighbours-q01", "text": "Which of these neighbouring kinds and how to tell them apart hold for the sense of sorting algorithm this model covers, and on what evidence?", "kind": "provenance" } ] } ] } ] } ] }, "openQuestions": [ "Does the registry intend sorting networks, external sorting and distributed sorting to be variants within this entry or linked specialised concepts?", "Which authoritative sources should establish the shared sorting contract and the evidence standard for individual algorithm guarantees?", "What convention should this catalogue use for in-place sorting, particularly when recursion stacks or indirect permutation outputs require storage?", "How should the model represent partial-order inputs: require an explicit ordering extension or link the task to a neighbouring model such as topological sorting?", "What evidence is sufficient to mark a particular variant ready for use when correctness arguments, implementation validation and workload measurements provide different levels of assurance?" ], "statistics": { "bundles": 6, "layers": 11, "findings": 18, "questions": 28 } }, "draft": { "generator": "vr.draft.v3", "status": "draft-generated", "researched": false, "archetype": "work, medium or creative form", "method": "Written from the archetype playbook - what this kind of thing needs beyond identity and provenance - and from the structure that recurred across 6,333 models already researched by two engines. Applied to this entry by rule. No source was read for this thing and no claim here is researched. This entry carries no facets of its own, so they were inferred from its domain - a guess about a whole domain applied to one thing.", "facetsInferred": true, "nextPass": "A researcher replaces this draft with a sourced specification. Treat every sentence below as a proposal to argue with.", "purpose": "Give an agent a durable, checkable way to recognise a sorting algorithm, record what state it is in, and decide what may be done with it.", "whatItIs": "Enable an AI agent to recognise a sorting algorithm, assess its ordering guarantees and resource demands, and decide whether and how it may be used for a particular sorting task.", "characteristics": { "substance": "information", "origin": "conceptual", "agency": "inert" }, "whatYouCanDoWithIt": [ "read and interpreted", "observed and measured" ], "distinguishingFeatures": [ "Names folded into this entry, which a task may need to split apart again: quantum sort, topological sorting algorithm, flashsort, Manchester_triage, merge sort, Canadian Triage and Acuity Scale, external sorting, Stupid sort, JumpSTART triage, comparison sort, stable sorting algorithm, adaptive sort.", "19 finer distinctions are held as aliases rather than separate entries, because telling them apart needs a task that asks for it.", "Described in 60 Wikipedia languages, which is a measure of how widely the thing is known, not of how important it is." ], "openQuestionsForResearch": [ "Which of the bundles below does a real task actually need, and which are ceremony?", "What does this thing have that the facets do not capture at all?", "Which neighbouring kind is most often confused with a sorting algorithm, and on what evidence are they told apart?" ], "whatItIsMadeOf": "content that has to be carried by something else", "physicalCharacter": [ "Does nothing on its own; everything it does, something else did to it.", "These come from the domain this entry sits in rather than from the entry itself, so treat them as a first guess about the whole domain applied to one thing." ], "whatCanBeDoneWithIt": [ "read it and act on what it says", "observe it, measure it, record its state" ], "howItIsRecognised": [ "What is seen is a copy or a performance, not the work. Recognising the work means recognising the content through whatever is carrying it." ], "relatedModels": [ { "relation": "covers", "note": "Finer kinds folded into this entry because telling them apart needs a task that asks for it. Each is a model waiting to be split out when one does.", "targets": [ "quantum sort", "topological sorting algorithm", "flashsort", "Manchester_triage", "merge sort", "Canadian Triage and Acuity Scale", "external sorting", "Stupid sort", "JumpSTART triage", "comparison sort", "stable sorting algorithm", "adaptive sort" ] } ], "standing": "Described in 60 Wikipedia languages, which measures how widely it is written about rather than how important or how common it is. 19 finer distinctions are held inside this entry as names rather than as separate models.", "structure": { "bundles": [ { "id": "identity-and-classification", "name": "Identity, naming and classification", "description": "How an agent tells one sorting algorithm from another, and a sorting algorithm from things that resemble it.", "rationale": "Recognition comes before every other claim. Without stable identity nothing else in the model can be trusted to be about the same thing twice.", "layers": [ { "id": "naming-and-identifiers", "name": "Names and identifiers", "description": "The names this thing goes by and the identifiers that survive translation and time.", "findings": [ { "id": "preferred-name-and-aliases", "name": "Preferred name, aliases and local names", "description": "Which name to use, which names mean the same thing, and which merely sound similar.", "questions": [ { "id": "preferred-name-and-aliases-q01", "text": "What identifies and describes the name of a sorting algorithm, and in what units or vocabulary?", "kind": "definition", "answer_data": [ "identifiers", "types and classes", "values with units", "explicit unknowns" ] }, { "id": "preferred-name-and-aliases-q02", "text": "Who or what asserted this about the name of a sorting algorithm, by which method, and when was it true?", "kind": "provenance", "answer_data": [ "authority", "method", "evidence", "event time", "knowledge time" ] }, { "id": "preferred-name-and-aliases-q03", "text": "What may an agent decide or do once the name of a sorting algorithm is known, and what must it refuse?", "kind": "action", "answer_data": [ "permitted actions", "preconditions", "refusals", "escalation" ] } ] }, { "id": "stable-identifiers", "name": "Stable identifiers and external keys", "description": "Identifiers that keep pointing at this kind of thing across systems and languages.", "questions": [ { "id": "stable-identifiers-q01", "text": "What identifies and describes an identifier for a sorting algorithm, and in what units or vocabulary?", "kind": "definition", "answer_data": [ "identifiers", "types and classes", "values with units", "explicit unknowns" ] }, { "id": "stable-identifiers-q02", "text": "Who or what asserted this about an identifier for a sorting algorithm, by which method, and when was it true?", "kind": "provenance", "answer_data": [ "authority", "method", "evidence", "event time", "knowledge time" ] }, { "id": "stable-identifiers-q03", "text": "What may an agent decide or do once an identifier for a sorting algorithm is known, and what must it refuse?", "kind": "action", "answer_data": [ "permitted actions", "preconditions", "refusals", "escalation" ] } ] } ] }, { "id": "classification-and-granularity", "name": "Classification and granularity", "description": "Where a sorting algorithm sits among kinds, and how finely a task needs to cut it.", "findings": [ { "id": "kind-and-parents", "name": "Kind, parents and neighbouring kinds", "description": "The classes this thing belongs to and the ones it is next to.", "questions": [ { "id": "kind-and-parents-q01", "text": "What identifies and describes the kind of a sorting algorithm, and in what units or vocabulary?", "kind": "definition", "answer_data": [ "identifiers", "types and classes", "values with units", "explicit unknowns" ] }, { "id": "kind-and-parents-q02", "text": "Who or what asserted this about the kind of a sorting algorithm, by which method, and when was it true?", "kind": "provenance", "answer_data": [ "authority", "method", "evidence", "event time", "knowledge time" ] }, { "id": "kind-and-parents-q03", "text": "What may an agent decide or do once the kind of a sorting algorithm is known, and what must it refuse?", "kind": "action", "answer_data": [ "permitted actions", "preconditions", "refusals", "escalation" ] } ] }, { "id": "distinguishing-features", "name": "Distinguishing features", "description": "What separates a sorting algorithm from the things most often confused with it.", "questions": [ { "id": "distinguishing-features-q01", "text": "What identifies and describes what distinguishes a sorting algorithm, and in what units or vocabulary?", "kind": "definition", "answer_data": [ "identifiers", "types and classes", "values with units", "explicit unknowns" ] }, { "id": "distinguishing-features-q02", "text": "Who or what asserted this about what distinguishes a sorting algorithm, by which method, and when was it true?", "kind": "provenance", "answer_data": [ "authority", "method", "evidence", "event time", "knowledge time" ] }, { "id": "distinguishing-features-q03", "text": "What may an agent decide or do once what distinguishes a sorting algorithm is known, and what must it refuse?", "kind": "action", "answer_data": [ "permitted actions", "preconditions", "refusals", "escalation" ] } ] } ] } ] }, { "id": "state-and-lifecycle", "name": "State and lifecycle", "description": "The states a sorting algorithm passes through and the events that move it between them.", "rationale": "Most decisions about a thing depend on what state it is in now, which is a claim with a time on it, not a property.", "layers": [ { "id": "lifecycle-stages", "name": "Lifecycle stages", "description": "From coming into existence to ceasing to be one of these.", "findings": [ { "id": "stages-and-transitions", "name": "Stages and transitions", "description": "The stages worth naming and what moves a sorting algorithm between them.", "questions": [ { "id": "stages-and-transitions-q01", "text": "What identifies and describes the lifecycle of a sorting algorithm, and in what units or vocabulary?", "kind": "definition", "answer_data": [ "identifiers", "types and classes", "values with units", "explicit unknowns" ] }, { "id": "stages-and-transitions-q02", "text": "Who or what asserted this about the lifecycle of a sorting algorithm, by which method, and when was it true?", "kind": "provenance", "answer_data": [ "authority", "method", "evidence", "event time", "knowledge time" ] }, { "id": "stages-and-transitions-q03", "text": "What may an agent decide or do once the lifecycle of a sorting algorithm is known, and what must it refuse?", "kind": "action", "answer_data": [ "permitted actions", "preconditions", "refusals", "escalation" ] } ] } ] }, { "id": "observations-and-status", "name": "Observations and current status", "description": "What is observed about a sorting algorithm, how often and by whom.", "findings": [ { "id": "observation-record", "name": "Observation record", "description": "How an observation of a sorting algorithm is recorded so that it can be superseded rather than overwritten.", "questions": [ { "id": "observation-record-q01", "text": "What identifies and describes an observation of a sorting algorithm, and in what units or vocabulary?", "kind": "definition", "answer_data": [ "identifiers", "types and classes", "values with units", "explicit unknowns" ] }, { "id": "observation-record-q02", "text": "Who or what asserted this about an observation of a sorting algorithm, by which method, and when was it true?", "kind": "provenance", "answer_data": [ "authority", "method", "evidence", "event time", "knowledge time" ] }, { "id": "observation-record-q03", "text": "What may an agent decide or do once an observation of a sorting algorithm is known, and what must it refuse?", "kind": "action", "answer_data": [ "permitted actions", "preconditions", "refusals", "escalation" ] } ] } ] } ] }, { "id": "content-and-access", "name": "Content, encoding and access", "description": "What a sorting algorithm says, how it is encoded and who may read it.", "rationale": "An informational thing carries content that can be copied, versioned and withheld, none of which its physical carrier explains.", "layers": [ { "id": "content-and-encoding", "name": "Content and encoding", "description": "The content itself, its format and its language.", "findings": [ { "id": "content-and-format", "name": "Content, format and language", "description": "What a sorting algorithm contains and in what form it is held.", "questions": [ { "id": "content-and-format-q01", "text": "What identifies and describes the content of a sorting algorithm, and in what units or vocabulary?", "kind": "definition", "answer_data": [ "identifiers", "types and classes", "values with units", "explicit unknowns" ] }, { "id": "content-and-format-q02", "text": "Who or what asserted this about the content of a sorting algorithm, by which method, and when was it true?", "kind": "provenance", "answer_data": [ "authority", "method", "evidence", "event time", "knowledge time" ] }, { "id": "content-and-format-q03", "text": "What may an agent decide or do once the content of a sorting algorithm is known, and what must it refuse?", "kind": "action", "answer_data": [ "permitted actions", "preconditions", "refusals", "escalation" ] } ] } ] }, { "id": "access-and-rights", "name": "Access, rights and retention", "description": "Who may read, copy or change it, and for how long it is kept.", "findings": [ { "id": "access-rules", "name": "Access rules and retention", "description": "The permissions attached to a sorting algorithm and the period it survives.", "questions": [ { "id": "access-rules-q01", "text": "What identifies and describes access to a sorting algorithm, and in what units or vocabulary?", "kind": "definition", "answer_data": [ "identifiers", "types and classes", "values with units", "explicit unknowns" ] }, { "id": "access-rules-q02", "text": "Who or what asserted this about access to a sorting algorithm, by which method, and when was it true?", "kind": "provenance", "answer_data": [ "authority", "method", "evidence", "event time", "knowledge time" ] }, { "id": "access-rules-q03", "text": "What may an agent decide or do once access to a sorting algorithm is known, and what must it refuse?", "kind": "action", "answer_data": [ "permitted actions", "preconditions", "refusals", "escalation" ] } ] } ] } ] }, { "id": "work-and-manifestation", "name": "Work, version and copy", "description": "Which level of sorting algorithm a statement is about.", "rationale": "The work, the edition, the file and the copy in hand are four things; rights and content attach to different ones.", "layers": [ { "id": "levels", "name": "Levels of the thing", "description": "Work, expression, manifestation and item, in plain terms.", "findings": [ { "id": "level-rules", "name": "What belongs at each level", "description": "Which facts hold for the work and which only for one copy.", "questions": [ { "id": "level-rules-q01", "text": "For sorting algorithm, which facts belong to the work itself, which to a version, and which to a single copy?", "kind": "boundary" }, { "id": "level-rules-q02", "text": "What identifier exists at each level, and which one is being cited?", "kind": "definition" } ] } ] }, { "id": "versions", "name": "Versions, editions and variants", "description": "How versions differ and which is canonical to whom.", "findings": [ { "id": "version-record", "name": "Versions and canonicity", "description": "Differences that matter and who calls one authoritative.", "questions": [ { "id": "version-record-q01", "text": "Which versions or editions of sorting algorithm exist, and how do they differ substantively?", "kind": "definition" }, { "id": "version-record-q02", "text": "Who treats which version as authoritative, and for what purpose?", "kind": "provenance" } ] } ] } ] }, { "id": "authorship-and-rights", "name": "Authorship, rights and permitted use", "description": "Who made sorting algorithm and what may be done with it.", "rationale": "Rights are jurisdictional, time-limited and attached to a level, and an agent that ignores that will copy what it may not.", "layers": [ { "id": "authorship", "name": "Authorship and contribution", "description": "Who contributed what, and in what capacity.", "findings": [ { "id": "contribution-record", "name": "Contributors and roles", "description": "The people and bodies behind it, with their roles.", "questions": [ { "id": "contribution-record-q01", "text": "Who authored or contributed to sorting algorithm, in what roles, and how is that attested?", "kind": "provenance" }, { "id": "contribution-record-q02", "text": "Where authorship is disputed or anonymous, what is recorded instead?", "kind": "boundary" } ] } ] }, { "id": "rights", "name": "Rights and permissions", "description": "Which rights subsist, where, until when, and what they permit.", "findings": [ { "id": "rights-record", "name": "Rights, term and permitted acts", "description": "The regime in force and what it allows.", "questions": [ { "id": "rights-record-q01", "text": "What rights subsist in sorting algorithm, in which jurisdictions, and until when?", "kind": "definition" }, { "id": "rights-record-q02", "text": "Which acts are permitted without further permission, and which must an agent refuse?", "kind": "action" } ] } ] } ] }, { "id": "provenance-and-evidence", "name": "Provenance, evidence and time", "description": "Where every claim about a sorting algorithm came from and when it held.", "rationale": "A claim without a source and a time cannot be superseded, only overwritten, and an agent that overwrites loses the ability to explain itself.", "layers": [ { "id": "source-and-authority", "name": "Source and authority", "description": "Who said it, on what evidence, and how strongly.", "findings": [ { "id": "claim-provenance", "name": "Claim provenance and confidence", "description": "The authority behind each claim about a sorting algorithm and how confident it is.", "questions": [ { "id": "claim-provenance-q01", "text": "What identifies and describes a claim about a sorting algorithm, and in what units or vocabulary?", "kind": "definition", "answer_data": [ "identifiers", "types and classes", "values with units", "explicit unknowns" ] }, { "id": "claim-provenance-q02", "text": "Who or what asserted this about a claim about a sorting algorithm, by which method, and when was it true?", "kind": "provenance", "answer_data": [ "authority", "method", "evidence", "event time", "knowledge time" ] }, { "id": "claim-provenance-q03", "text": "What may an agent decide or do once a claim about a sorting algorithm is known, and what must it refuse?", "kind": "action", "answer_data": [ "permitted actions", "preconditions", "refusals", "escalation" ] } ] } ] }, { "id": "time-and-versions", "name": "Time, versions and supersession", "description": "When a claim was true, when it was learnt, and what replaced it.", "findings": [ { "id": "validity-and-supersession", "name": "Validity period and supersession", "description": "How an old claim about a sorting algorithm is retired without being erased.", "questions": [ { "id": "validity-and-supersession-q01", "text": "What identifies and describes the validity of a claim about a sorting algorithm, and in what units or vocabulary?", "kind": "definition", "answer_data": [ "identifiers", "types and classes", "values with units", "explicit unknowns" ] }, { "id": "validity-and-supersession-q02", "text": "Who or what asserted this about the validity of a claim about a sorting algorithm, by which method, and when was it true?", "kind": "provenance", "answer_data": [ "authority", "method", "evidence", "event time", "knowledge time" ] }, { "id": "validity-and-supersession-q03", "text": "What may an agent decide or do once the validity of a claim about a sorting algorithm is known, and what must it refuse?", "kind": "action", "answer_data": [ "permitted actions", "preconditions", "refusals", "escalation" ] } ] } ] } ] } ] }, "statistics": { "bundles": 6, "layers": 12, "findings": 14, "questions": 38 } } } }