algorithm-radix-sort

The groupant beside algorithms/src/radix_sort/mod.rs in the Mova repository: what the code computes, what it never does, how to go back from its outputs, its invariants, cost and checks.

Facts

Implementation material. A Mova code model describes this code at one source revision: partial models, finite checks and their stated scope. It is not a reviewed general exposition, and its labels are shown as written, never raised.

Components

component	label	where
approximant	bounded checked	Forward
ast	partial	`syntax.json`
cost	symbolic unmeasured	Cost
descriptant	present	descriptant
invariant	source derived	Invariant
tests	bounded executed	evidence

Obernants

The typed relations around the forward model: the behaviour complement (what the code never does), the reverse reconstruction (every input compatible with an output) and specialised views.

id	type	label	where
`nonbehavior`	behavior_complement	partial source derived	nonbehavior
`preimages`	reverse_reconstruction	partial source derived	preimages
`idempotence`	metamorphic_relation	partial source derived	idempotence
`pass-shuffle-fiber`	reverse_reconstruction	partial source derived	pass-shuffle-fiber
`pass-composition`	composition_relation	partial source derived	pass-composition
`monotone-relabel`	metamorphic_relation	partial source derived	monotone-relabel
`scratch-boundary`	resource_preimage	partial source derived	scratch-boundary
`bucket-partition`	conservation_relation	partial source derived	bucket-partition

Model text

descriptant

radix_sort mod.rs epoch memory

2026-10-30. Repository search found no matching implementation in algorithms/src or math/src. Original English std-only code; no external solution imports. Prospective mathematics preceded implementation and remains in mod.rs.groupant/prospective.md.

Four tests pass in debug and release. All 21,845 arrays of lengths 0..7 over {0,255,256,u64::MAX} match std slice sorting. An 8,192-value fixed-seed full-width array and individual-byte/extreme fixtures match. An internal pass test compares each byte against stable std sort_by_key. Allocator exhaustion is not injected; allocation error atomicity follows source ordering only. A compiled mutant skipping the highest byte pass is rejected by full_width_boundaries_and_idempotence.

The combiner relates raw source, partial syntax, forward relation, typed obernants, invariant, cost and finite evidence. Preserve predictions and rejected mutants across future epochs. Internal radix byte stability is observable via distinct values sharing a digit; whole-sort payload stability is not exposed. Missing universal proof, allocator-exhaustion injection and downstream wiring remain explicit. Exact algorithms require no invented approximant profiles. Future executable approximants must honor 1%, 2%, 5%, 10% caps and source/evidence binding.

Added histogram and digit-subsequence fibers, bounded monotone transforms and explicit resource or pass-composition boundaries. The model distinguishes whole-sort order loss from pass-local subsequence retention. Three new Rust relation tests per algorithm reject explicit false premises. The implementation and public API remain unchanged. Models retain allocator uncertainty and scalar stability limits. No timing claim or approximate execution profile is introduced; supported caps remain at most 10%.

Finite confirmation: debug/release twice and strict Clippy passed; all six targeted compiled mutant checks showed red. The monotone relation alone admits a minimum-only implementation, so multiplicity-fiber checks remain independently necessary. See evidence.md for the preserved surviving countermodel and log hashes.

model

radix_sort mod.rs model

Forward

For length below two return Ok unchanged. Otherwise reserve n scratch values before writes; reserve failure returns TryReserveError with unchanged input. Eight stable byte passes in increasing significance yield the unique ascending permutation, preserving all multiplicities.

Invariant

At each byte pass counts sum to n; prefix cursors partition destination into disjoint buckets. Traversing source left-to-right preserves relative order within a digit. After k passes values are sorted by their k lowest bytes; after eight this is unsigned u64 order. Explicit little-endian byte extraction is host independent.

Cost

O(8(n+256)) time and O(n+256) auxiliary elements; eight copies of n values. Trivial inputs O(1). No timing measurements.

nonbehavior

Type: behavior_complement. For observations (input, allocator outcome, Result, output), exclude nonascending success, changed length or multiset, mutation on reserve error, or failure after any byte pass. Internal pass observations exclude decreasing digit order or reversal within equal-digit source subsequences.

preimages

Type: reverse_reconstruction. Given successful sorted output y, compatible original inputs are all permutations of its multiset; allocation must succeed unless len<2. Err admits the unchanged input and failed reserve. For an internal digit-pass result, predecessors are shuffles of digit subsequences preserving order within each digit. Sorting is not injective; no unique original ordering is claimed.

idempotence

Type: metamorphic_relation. S(S(x))=S(x). Each byte pass preserves every digit subsequence. Tests use distinct scalar values sharing selected byte keys to observe internal pass stability; scalar full-sort equality cannot demonstrate attached payload stability.

pass-shuffle-fiber

Type: reverse_reconstruction. Domain: Private byte_pass with byte 0..7, equal source/destination lengths, arbitrary u64 values.

For fixed byte b and digit-sorted y, P_b(x)=y iff for every digit d the subsequence of x with digit d equals that of y in order. Thus predecessors are interleavings of fixed digit subsequences, not arbitrary multiset permutations. Distinct values [0x300,0x100,0x201,0x001] give six accepted shuffles at byte zero; reversing a same-digit pair is rejected.