radsort

radsort is a #![no_std] Rust crate that implements LSB radix sort for sorting slices by scalar keys: booleans, characters, integers, and floating-point numbers, including tuples of these types for multi-key sorting. It converts every supported scalar into an order-preserving unsigned integer key (flipping the sign bit for signed integers, and flipping sign-plus-magnitude bits for IEEE 754 floats) so the whole sort can run as byte-wise counting sort passes.

The crate ships three entry points — a direct sort, a sort_by_key variant that takes a key-extraction closure, and a sort_by_cached_key variant that caches extracted keys before reordering, which pays off for expensive key functions or large elements. Stability is guaranteed (equal elements keep their relative order), and an unopt module exposes versions without the digit-skipping optimization for consistent, benchmarkable performance. It is regularly benchmarked against slice::sort/slice::sort_unstable and typically wins on slices of a few hundred elements or more.

What You Get

• Direct sort() for slices of built-in scalar types (bool, char, all integer widths, f32/f64)
• sort_by_key() for sorting arbitrary structs via a key-extraction closure
• sort_by_cached_key() for expensive key functions or large elements, using an indices-based indirect sort
• Multi-key sorting by passing tuples of up to four scalar keys, most significant first
• An unopt module with non-skipping variants for predictable, benchmark-friendly timing
• #![no_std] support (needs only alloc) so it can run in embedded and other no-std environments

Common Use Cases

• Sorting large numeric datasets (timestamps, ids, measurements) faster than comparison sorts
• Sorting game or simulation entities by one or more numeric properties each frame
• Sorting structs by an expensive-to-compute or large key using the cached-key variant
• Multi-key sorts (e.g. sort by category, then by score) without writing a custom comparator
• Running in no_std contexts such as embedded targets or custom runtimes that still have an allocator

Under The Hood

Architecture The crate is a small, cleanly layered library: lib.rs exposes the public sort/sort_by_key/sort_by_cached_key functions and the sealed Key trait (implemented for all scalar types and tuples up to four elements), scalar.rs implements a separate Scalar trait that maps each scalar type to an order-preserving unsigned RadixKey, sort.rs implements the actual LSB radix/counting sort as a macro-generated radix_sort_u32/radix_sort_usize pair per key width, and double_buffer.rs provides a DoubleBuffer abstraction over MaybeUninit slices whose Drop impl guarantees the caller’s slice is left in a valid, fully-initialized state even if the user’s key function panics mid-sort. Both Key and Scalar are sealed via a private Sealed trait, closing the API to downstream implementations and keeping the crate’s invariants — particularly the safety of the unsafe scatter/swap operations in DoubleBuffer — fully under its own control.

Tech Stack Pure Rust with zero external dependencies (Cargo.toml declares no [dependencies] entries at all), built with #![no_std] plus extern crate alloc for Vec/Box. It targets Rust 1.60+, uses core::mem::MaybeUninit and raw pointer copies for the double-buffered scatter, and is packaged as a standard cargo library crate with no build-time codegen beyond Rust’s own macro system, which it uses heavily to generate per-width sort implementations and per-type key conversions without runtime dispatch.

Code Quality The crate has real test coverage: scalar.rs carries unit tests that verify every to_radix_key conversion preserves ordering (including exhaustive bit-pattern tests for float NaN/infinity/subnormal edge cases), and tests/integration_tests.rs exercises sort, sort_by_cached_key, and struct/reference sorting end to end. CI (GitHub Actions) runs cargo fmt --check, cargo clippy --all-targets with warnings denied, cargo test, and — notably for a crate built on unsafe pointer manipulation — cargo miri test across four target/endianness combinations (64-bit and 32-bit, little- and big-endian), which is a stronger safety bar than most small crates apply to their unsafe code.

What Makes It Unique Radix sort itself is a well-known algorithm, but radsort’s specific contribution is a digit-skipping optimization: before sorting, it inspects the histogram of each key byte and skips any digit where every element already falls in the same bucket, which can cut the sorting time dramatically for keys with a narrow effective range (e.g. small integers stored in a wide type). It pairs this with a size-adaptive indirect sort for sort_by_cached_key — choosing u8/u16/u32/usize index widths based on slice length to shrink the temporary allocation — and a panic-safe double-buffer design that keeps the crate sound even when caller-provided key functions misbehave.