sorting algorithm

Admissible ordering

Record the input scope and the properties required of comparisons or sortable keys.

1. What collection is sorted, which keys or comparisons establish order, and what properties must that order satisfy? definition
2. How are equivalent keys, missing values, incomparable values and exceptional numeric values treated or excluded? boundary

Sorted permutation

Record how the result demonstrates sortedness while preserving every input occurrence.

1. What postcondition establishes sortedness, and does the result rearrange elements, copy them or return a permutation of references? definition
2. How must the result preserve multiplicities and, when stability is required, the relative order of equivalent elements? boundary

Ordering procedure

Record the defining steps, primitive operations and progress rule.

1. Which steps establish order, such as partitioning, merging, insertion, heap operations or distribution by key digits? definition
2. Which readable algorithm description or pseudocode defines those steps and their stopping conditions? provenance

Material variant choices

Record consequential choices such as pivot rules, radix, merge scheduling and fallback thresholds.

1. Which choices define this variant, including any randomness, hybrid stages or fallback method? definition
2. Which guarantees must be reassessed before changing one of those choices? action

Guarantee support

Record evidence for each correctness property and the assumptions on which it depends.

1. What invariants and progress argument establish sortedness, element preservation and termination? definition
2. Which sources support those guarantees and any stability claim for this exact variant? provenance

Sorting validation

Record checks capable of detecting ordering, preservation and stability failures.

1. Which checks independently verify output order, input multiplicities and required stability? action
2. Which boundary inputs exercise this method's failure modes, including empty inputs, equivalent keys and adverse input arrangements? boundary

Time and space costs

Record time and auxiliary storage bounds without hiding key processing, recursion or buffering.

1. What time bounds apply by case, under which cost model and parameters, and what distribution or randomness supports average or expected claims? measurement
2. What auxiliary storage is required, and does the accounting include recursion, temporary buffers and output storage? measurement

Adaptivity and pathologies

Record favourable and adverse workloads and the evidence separating them.

1. How do existing runs, inversions, duplicate keys, key width or key range affect the relevant operation counts? measurement
2. Which inputs trigger worst-case behaviour, and what evidence supports any proposed mitigation? boundary

Access and movement preconditions

Record the operations the input representation and execution environment must support.

1. Does this procedure require random access, repeated passes, writable storage, movable elements or specific key operations? boundary
2. Which adaptations are required for linked sequences, external storage or parallel execution, and which guarantees would need revalidation? action

Sorting task fit

Record why the algorithm is usable, unsuitable or insufficiently assessed for a stated workload.

1. Do the task's ordering, stability, mutation, memory and latency requirements fit the guarantees under the anticipated workload? action
2. What additional evidence or adaptation is needed before selecting an implementation and executing it? action

Kinds and varieties

Reported by the breadth pass; each item needs checking against its source before it becomes normative.

• 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)

1. Which of these kinds and varieties hold for the sense of sorting algorithm this model covers, and on what evidence? provenance

Identifiers and schemes

Reported by the breadth pass; each item needs checking against its source before it becomes normative.

• Wikidata - Q128317 - Item for the class "sorting algorithm"; individual named methods have their own items.
• ACM Computing Classification System (2012) - Theory of computation → Design and analysis of algorithms → Sorting and searching - Concept heading, not a numeric instance identifier for a particular algorithm.
• ISO C library - qsort - Identifier of the standard C sorting function in <stdlib.h> (ISO/IEC 9899).
• ISO C++ standard library - std::sort | std::stable_sort | std::partial_sort - Canonical C++ algorithm names (ISO/IEC 14882).

1. Which of these identifiers and schemes hold for the sense of sorting algorithm this model covers, and on what evidence? provenance

Standards and regulation

Reported by the breadth pass; each item needs checking against its source before it becomes normative.

• 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

1. Which of these standards and regulation hold for the sense of sorting algorithm this model covers, and on what evidence? provenance

Real-world use

Reported by the breadth pass; each item needs checking against its source before it becomes normative.

• 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

1. Which of these real-world use hold for the sense of sorting algorithm this model covers, and on what evidence? provenance

Typical measurements

Reported by the breadth pass; each item needs checking against its source before it becomes normative.

• Comparison count (comparison sorts) - 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 - comparisons
• Asymptotic time - O(n log n) typical library default; O(n) for integer/radix sorts under bounded keys; O(n²) worst case without introspective fallback - element operations
• Extra working memory - O(1) words (true in-place) through O(log n) (typical quicksort/introsort stack) to O(n) (mergesort, counting/radix auxiliary arrays) - machine words or records
• Input size encountered in practice - tens of elements in UI widgets; 10^6-10^9 in-memory; 10^12+ in external/distributed sorts - records
• Recursion or call-stack depth - O(log n) with balanced or introspective control; O(n) for naive quicksort on adversarial input - frames

1. Which of these typical measurements hold for the sense of sorting algorithm this model covers, and on what evidence? provenance

Failure modes and hazards

Reported by the breadth pass; each item needs checking against its source before it becomes normative.

• 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

1. Which of these failure modes and hazards hold for the sense of sorting algorithm this model covers, and on what evidence? provenance

Regional variation

Reported by the breadth pass; each item needs checking against its source before it becomes normative.

• 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

1. Which of these regional variation hold for the sense of sorting algorithm this model covers, and on what evidence? provenance

Neighbouring kinds and how to tell them apart

Reported by the breadth pass; each item needs checking against its source before it becomes normative.

• Selection / order-statistic algorithm (e.g. quickselect) - Returns the k-th ordered element (or partitions around it) without putting every element into final position; a full sort orders all positions.
• Collation algorithm (Unicode UCA and locale tailorings) - Defines the total order on strings; a sorting algorithm only applies some already-given order to permute records.
• Priority queue / binary heap - Maintains a partial order so the next extremum can be extracted; it yields a fully sorted sequence only if used as heapsort.
• Topological sort - Linearises a directed acyclic graph consistently with a partial order on vertices; it does not sort arbitrary totally ordered keys.
• Searching algorithm - Locates a key in a collection; it does not rearrange the collection into sorted order (though binary search assumes that order already holds).
• Shuffle / random permutation - Draws an (often uniform) unordered rearrangement; a sort aims at a specific total order, not mixing.
• Hash partitioning / grouping - Clusters equal keys or buckets by hash without placing distinct keys into sorted sequence.

1. 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? provenance