Insertion sort over a finite domainExhaustive bounded validation · 364 inputs
The problem
Sort every list of length 0–5 over {−1, 0, 1}, preserving every occurrence.
The checked result
Correct over the stated input domain: yes.
The candidate shifts larger values to the right before inserting the next value. A separate checker compares every declared input with Python’s reference ordering. Duplicates and the empty list are included.
Why the checker accepts it
- Enumerate every list in the declared alphabet and length bound.
- Run the candidate insertion-sort implementation without modifying the source input.
- Compare each result with the reference ordering, including repeated elements.
- Reject immediately with an input witness if ordering or multiplicity differs.
Formal specification
{
"alphabet": [
-1,
0,
1
],
"max_length": 5
}Claim and evidence
{
"claim": {
"correct_on_declared_domain": true
},
"witness": {
"function": "insertion_sort"
}
}Dataset construction
Deterministic finite fixture; full enumeration or witness replay as stated. Structured JSON; field meanings are stated in the specification. Acceptance covers 364 checker units for this record; the unit type is stated in its verification scope.
Complexity and limits
For alphabet size k and maximum length n, this family checks Σ kⁱ inputs for i=0…n. Insertion sort performs O(n²) comparisons in its worst case.
This is not a general proof for arbitrary lists, a stability proof, or a complexity result.
A boundary to investigate
Sortedness alone does not prove that an output preserves the input multiset. Add stability certificates for tagged records or an unbounded inductive invariant.