Lattice Sort (latticesort) is a zero-dependency, 100% safe Rust sorting library for primitive integers (i32, u32, i64, u64) and floating-point slices (f32, f64). Developed through an autonomous experimental research campaign (autoresearch) and hardened against an adversarial red-team suite, Lattice Sort holds a 7.41x geometric-mean speedup at std::slice::sort_unstable (ipnsort / pattern-defeating quicksort), with up to 7.68x recorded at Uniform 32-bit Random (2.7x) is the only distribution that stresses the general 4-pass cascade.
-
Order Theory and Abstract Algebra: In discrete mathematics and Computer Science, a lattice is a partially ordered set
$(L, \le)$ in which every pair of elements$(a, b)$ has a unique supremum (join, $a \vee b = \max(a, b)$) and a unique infimum (meet, $a \wedge b = \min(a, b)$). Every totally ordered numeric domain sorted by this library (i32,u32,i64,u64, and total-orderf32/f64) forms a distributive lattice. - Solid-State Physics and Hardware Cache Geometry: In physics, a crystal lattice is a periodic array of fixed spatial sites where particles settle into minimum-energy equilibrium positions. Instead of sorting via millions of pairwise element-to-element duels, Lattice Sort projects keys directly into fixed-address coordinate slots inside L1 (Level 1 Cache, the fastest cache memory core-local to the processor) and L2 (Level 2 Cache, the intermediate cache memory between L1 and shared cache).
- In Plain English: Traditional sorting works like a line of blindfolded people trying to line up by height by comparing themselves two at a time. Lattice Sort works like a hotel mailroom wall of numbered pigeonholes (a lattice): each number's own mathematical value tells it the exact pigeonhole where it belongs, skipping pairwise duels altogether.
Real-world lists often arrive with an existing shape: stock prices that rose until midday and then fell (a wave), reversed logs, or database tables that are already 90% sorted with a few new rows appended at the end.
- What standard algorithms do: Chop the entire list into pieces and start comparing items from scratch.
- What Lattice Sort does: It takes a quick glance at just 8 evenly spaced spots in the list. When it sees a rising-then-falling wave (or a falling-then-rising valley), it grabs both ends of the wave and pulls them together like a zipper, merging the two halves in a single pass.
Huge real-world datasets frequently repeat a small set of distinct values (customer ages, ratings from 1 to 100, status codes, or sensor tiers).
- What standard algorithms do: Shuffle the same duplicate numbers back and forth millions of times.
- What Lattice Sort does: It places a tiny 1024-slot counting tray inside the processor's fastest memory (L1) and simply tallies how many times each value appears: "the number 7 appeared 80,000 times; the number 12 appeared 90,000 times". At the end, it writes out eighty thousand 7s followed by ninety thousand 12s in one contiguous sweep.
- The Two-Coin Trick (Dual-Sentinel Invariant): Normally, to know whether a slot in a counting tray is empty or already holding a number, the computer must check a separate "occupied" checklist on every single item. Lattice Sort eliminates that checklist check: it pre-fills every slot in the tray with the number
0, except for the single slot where0itself belongs, where it places the number1. Because no slot starts out holding its own true owner, the processor immediately knows a slot is valid whenever the number inside matches the number being read.
Sometimes a list has thousands of different numbers, but they all sit within a compact range (such as salaries, temperatures, or product prices between $10 and $5,000).
- What standard algorithms do: Shuffle values across temporary arrays using comparisons.
- What Lattice Sort does: It measures the distance between the smallest and largest number in the list. When that distance fits inside fast processor memory, it lays down a numbered ruler from the minimum value to the maximum value, tallies how many items land on each millimeter mark, and reads the ruler from left to right. On financial and Pareto distributions, this is 11x faster than Rust's standard sort.
4. The Single-Pass Post Office Sorter that Skips Identical Zip Codes (Fused LSD Radix Sort with Byte Skip)
When numbers are completely random and span billions of values, Lattice Sort acts like an automated postal sorting machine that sorts letters digit by digit (first by street, then city, then state, then country), a technique known as LSD (Least Significant Digit, a radix sorting order that processes bytes from lowest to highest significance) radix sort.
- What classic Radix Sort does: Reads all 1 million letters to count the streets, moves all 1 million letters; reads all 1 million letters again to count the cities, moves all 1 million letters; repeating 8 full trips across memory.
- What Lattice Sort does:
- One-Trip Quadruple Tally: Reads the list once at the start and tallies all 4 byte positions (street, city, state, country) at the same time.
- Skipping Identical Digits: If the tally shows that all 1 million letters belong to the same country and state (which happens constantly with timestamps from the same year or positive integers in a bounded range), Lattice Sort skips those sorting passes in zero seconds, cutting memory traffic in half.
Some lists repeat a short pattern: round-robin shard IDs, weekday labels, tariff bands cycling by hour.
-
What standard algorithms do: compare and count all
$N$ items even though only$p$ of them ever differ. -
What Lattice Sort does: a period
pis a shift register: positionimust equal positioni - p. It screens$p \le 64$ against the first eight values, verifies the winner block by block against the first block, and only then writes. A periodic slice needs no counting at all: residuejappears$\lceil (n - j) / p \rceil$ times, so the output is a permutation of one period. Slices of 1,000,000 items with period 13 drop from0.72 msto0.30 ms. Non-periodic input pays three tenths of a microsecond.
Sorting 10 million items scattered across a giant warehouse takes a long time because workers spend all their time walking back and forth across the warehouse floor. In a computer, that distant warehouse is RAM (Random-Access Memory, the main system memory outside the processor), while the workbench right in front of the worker is L2 cache.
- What Lattice Sort does: For lists of 1.5 million items or more, it first groups the items by their highest byte, called the MSB (Most Significant Byte, the highest-order byte of a multi-byte word that partitions keys into coarse buckets), into 256 smaller neighborhood boxes. Each neighborhood box is small enough (~156 KB) to fit completely on the processor's L2 workbench, so the processor finishes each box at top speed without walking back to RAM, or hands different boxes to multiple processor cores simultaneously (5.05x faster than standard Rust).
Given an input slice
If the number of sign inversions
-
Strictly Ascending (
$m = n - 1$ ): Returns immediately in$O(n)$ with 0 writes. -
Strictly Descending (
$m = 0$ , valley at$n - 1$ ): Reverses$A$ in-place via$\lfloor n/2 \rfloor$ swaps. -
Crest-to-Trough Bitonic Envelope (
$\cap$ ,$A[0] \le \dots \le A[m]$ and$A[m+1] \ge \dots \ge A[n-1]$ ): Merges the ascending left slice$A[0 \dots m]$ (indexed forward by$i = 0 \to m$ ) and the descending right slice$A[m+1 \dots n-1]$ (indexed backward by$j = n-1 \to m+1$ ) in a single linear pass:
-
Plateau Snap-Back Invariant: When
$m \ge \frac{3}{4}n$ (long sorted prefix followed by an unsorted tail) and$A[0] = A[\lfloor m/2 \rfloor] = c$ , the prefix contains a constant plateau. If$A[m] > c$ , the split index snaps back to$m' = \max \lbrace idx \le m \mid A[idx] = c \rbrace$ , sorts the tail$A[m'+1 \dots n-1]$ , and splices the entire constant block$c$ into position in a singlecopy_within+filloperation without allocating a merge buffer.
To detect low-cardinality inputs (
For a 32-bit key
The algorithm selects the first multiplier
Let $s_0 = h_{\mu^}(0)$ be the home slot of key $d_0 = 0$, and choose $d_1 = \min \lbrace v \in \mathbb{Z}^+ \mid h_{\mu^}(v) \neq s_0 \rbrace$. Initialize the 1024-slot key array
Theorem: Prior to any insertion, $\forall x \in \mathbb{Z}{2^{32}}$, let $s = h{\mu^*}(x)$; then
-
Case 1 ($s = s_0$): By definition of $s = h_{\mu^}(x) = s_0$ and $h_{\mu^}(d_1) \neq s_0$, we have
$x \neq d_1 = K[s_0]$ . -
Case 2 ($s \neq s_0$): Since $h_{\mu^}(d_0) = s_0 \neq s = h_{\mu^}(x)$, we have
$x \neq d_0 = K[s]$ .
Consequently, a direct hit used[s] from the fast path of the inner loop:
The 128-element probe from Stage 2 yields a lower bound on the global span:
If
For 32-bit signed integers (as_chunks::<4>()):
where the Kronecker delta 0x80) on the most significant byte so two's-complement negative integers precede positive integers.
Degenerate-Byte Skipping: Before executing scatter pass
If only
When
Each bucket l2_local_3pass_radix_sort (or dispatched across CPU (Central Processing Unit, the primary processor executing program instructions) cores in parallel_lattice_sort).
To sort unsigned integers and IEEE (Institute of Electrical and Electronics Engineers, the standards body defining the 754 floating-point binary representation) 754 floating-point numbers using the signed integer kernels:
- Unsigned Integers (
u32/u64):
-
IEEE 754 Floating-Point (
f32/f64): In IEEE 754 sign-magnitude encoding, positive floats already ascend lexicographically with their bit pattern, whereas negative floats (sign_bit = 1) descend as magnitude increases. Defining the arithmetic sign-extension mask$M(bits) = \text{sar}(bits, w - 1) \wedge (2^{w-1} - 1)$ , the self-inverse bijection is:
This maps
- Hardware:
13th Gen Intel(R) Core(TM) i7-1360P(12 physical cores / 16 logical threads: 4 Performance-cores + 8 Efficiency-cores), with dynamic Turbo Boost enabled. - Cache Hierarchy: L1d
48 KiBper P-core (32 KiBper E-core), L21.25 MiBper P-core (9 MiBtotal across 6 instances), L318 MiBshared. - System & Compiler: Linux x86_64,
rustc(Edition 2024),-C opt-level=3, Link-Time Optimization (lto = true),codegen-units = 1. - Measurement Protocol & Thermal Variance: Each distribution is timed 5 times and reduced to its median, every output slice is verified element-for-element against
std::slice::sort_unstable, and the reported geometric mean carries a 95% bootstrap interval over the 45 timing samples. Repeat runs of one binary span about ±5%, so deltas smaller than the interval are treated as noise rather than as a result. The red-team suite interleaves Lattice Sort andstdsamples pairwise, uses 9 rounds per attack, and falsifies an attack when the lower quartile of the paired ratio drops below 0.95x. Quantile intervals replaced bare medians inexp22..exp28; earlier figures used 3 samples without any interval.
Executed via cargo bench --bench bench_literature across all 9 benchmark distributions:
| Literature Algorithm | Scientific Citation | Geometric Mean (9 Datasets) | Uniform 32-Bit Random | Speedup vs Lattice Sort |
|---|---|---|---|---|
Lattice Sort (latticesort) |
This crate (src/kernel_i32.rs) |
0.752 ms |
5.221 ms |
1.00x (Baseline) |
1. ipnsort (std::slice::sort_unstable) |
Bergdoll & Peters (2024), pattern-defeating network sort in Rust 1.81+ | 5.458 ms |
14.757 ms |
7.26x faster |
2. driftsort (std::slice::sort) |
Bergdoll & Peters (2024), modern stable merge sort in Rust 1.81+ | 4.603 ms |
16.466 ms |
6.12x faster |
| 3. Classic 4-Pass LSD Radix Sort | Seward (1954) / Knuth, The Art of Computer Programming Vol. 3 (1973) | 11.192 ms |
6.305 ms |
14.89x faster |
| 4. American Flag Sort (In-Place MSB Radix) | McIlroy, Bostic & McIlroy (1993), 256-ary cyclic bucket permutation | 14.121 ms |
18.904 ms |
18.79x faster |
| 5. Bentley-McIlroy 3-Way Quicksort | Bentley & McIlroy (1993), C qsort with DNF (Dutch National Flag, a three-way partitioning scheme dividing elements into less-than, equal-to, and greater-than regions) |
22.689 ms |
73.855 ms |
30.19x faster |
| 6. Floyd Bottom-Up HeapSort | Williams & Floyd (1964), in-place binary heap sort | 68.972 ms |
109.284 ms |
91.78x faster |
| Dataset Distribution | Lattice Sort (ms) |
std::sort_unstable (ms) |
Speedup vs std
|
Active Stage |
|---|---|---|---|---|
1. Cyclic K=12
|
0.281 |
3.603 |
12.80x | Periodic Reconstruction (period 12) |
2. Cyclic K=13
|
0.324 |
2.880 |
8.88x | Periodic Reconstruction (period 13) |
3. Cyclic K=17 (prime) |
0.318 |
3.158 |
9.92x | Periodic Reconstruction (period 17) |
4. Wide K=13 (span |
0.783 |
3.052 |
3.90x | Dual-Sentinel L1 Hash Aggregation |
5. Random K=100
|
0.826 |
5.240 |
6.35x | Dual-Sentinel L1 Hash Aggregation |
6. Random K=1000
|
0.683 |
6.884 |
10.08x | Dense Range Counting (span 1000) |
| 7. Bitonic Soliton Wave ( |
1.208 |
14.656 |
12.14x | Bitonic Run Merger ($O(n)$) |
| 8. Pareto Power-Law | 0.894 |
6.691 |
7.48x | Dense Range Counting |
| 9. Uniform 32-bit Random | 5.223 |
14.120 |
2.70x | 4-Pass Fused LSD Radix Sort |
| Geometric Mean ( |
0.746 |
5.531 |
7.41x | Full Adaptive Pipeline |
| Dataset Distribution ( |
Lattice Sort (ms) |
std::sort_unstable (ms) |
Speedup vs std
|
Active Stage |
|---|---|---|---|---|
1. Cyclic K=12
|
5.89 |
30.18 |
5.12x | Periodic Reconstruction (period 12) |
2. Cyclic K=13
|
5.80 |
31.07 |
5.35x | Periodic Reconstruction (period 13) |
3. Cyclic K=17 (prime) |
5.71 |
34.16 |
5.98x | Periodic Reconstruction (period 17) |
4. Wide K=13 (span |
9.28 |
29.95 |
3.23x | Dual-Sentinel L1 Hash Aggregation |
5. Random K=100
|
9.38 |
47.80 |
5.09x | Dual-Sentinel L1 Hash Aggregation |
6. Random K=1000
|
11.91 |
69.00 |
5.79x | Dense Range Counting |
| 7. Bitonic Soliton Wave ( |
19.81 |
195.48 |
9.87x | Bitonic Run Merger ($O(n)$) |
| 8. Pareto Power-Law | 11.85 |
69.92 |
5.90x | Dense Range Counting |
| 9. Uniform 32-bit Random | 58.17 |
158.09 |
2.72x | Hybrid MSB + L2-Local 3-Pass Radix |
| Geometric Mean ( |
12.33 |
59.50 |
4.83x | Full Adaptive Pipeline |
| Type and Distribution ( |
Lattice Sort (ms) |
std::sort_unstable (ms) |
Speedup vs std
|
|---|---|---|---|
1. u32 (Uniform 32-bit) |
7.10 |
14.26 |
2.01x |
2. i64 (Timestamps: 4 constant upper bytes skipped) |
12.40 |
14.84 |
1.29x |
3. i64 (Low-Cardinality K=50 64-bit keys) |
1.68 |
4.55 |
2.70x |
4. u64 (Bounded 32-bit keys in u64) |
10.29 |
16.32 |
1.59x |
5. f32 (Signed IEEE 754 floats +/-) |
6.01 |
24.52 |
4.08x |
6. f64 (Sensor readings K=64 +/-, zero-alloc L1 hash) |
1.49 |
5.42 |
3.64x |
5. Multi-Core Parallel Execution (par_lattice_sort / parallel_lattice_sort) and 1-Billion-Element Scale ($4.00\text{ GB}$ )
| Uniform 32-Bit Scenario | parallel_lattice_sort |
Single-Thread Lattice Sort |
std::sort_unstable (ipnsort) |
Parallel Speedup vs std
|
Single-Thread Speedup vs std
|
|---|---|---|---|---|---|
|
|
2.05 ms |
5.41 ms |
15.02 ms |
7.33x | 2.68x |
|
|
14.26 ms |
64.87 ms |
181.98 ms |
12.76x | 2.49x |
2.913 s (343.2M/s) |
7.966 s (125.5M/s) |
22.371 s (44.7M/s) |
7.68x | 2.81x |
Ratios come from paired interleaved samples (Lattice Sort and std alternating inside one round), 9 rounds at
| Adversarial Attack Vector |
std
|
std
|
Verdict |
|---|---|---|---|
1A. Iceberg Attack (95% constant 0 + 5% random tail) |
2.58x | 2.13x | Survived |
| 1B. Mid-Array Entropy Trap (200 keys hidden at 45%..65%) | 3.00x | 3.08x | Survived |
| 1C. Sentinel & 24-Way Hash Collision Torture | 4.50x | 3.54x | Survived |
| 2A. Cutoff Boundary Uniform Random ( |
1.27x | 1.66x | Survived |
2B. Mid-Point Single Swap (swap(n/2 - 2, n/2 - 1)) |
1.58x | 1.45x | Survived |
| 3A. Fake Soliton (92% ascending ramp + 8% oscillating tail) | 7.83x | 7.70x | Survived |
| 3B. Valley Soliton ( |
11.80x | 13.22x | Survived |
4A. Sparse Horizon (K=150 keys, span |
3.11x | 3.86x | Survived |
| 4B. Exact Golden-Stride Probe Spoof (planted zeros at stride) | 2.31x | 2.85x | Survived |
| 5A. Periodic Spoof (periodic up to 99% of the slice) | 2.91x | n/a |
Survived |
cargo add latticesortuse latticesort::{LatticeSortExt, parallel_lattice_sort};
fn main() {
// 1. Polymorphic slice sorting via LatticeSortExt (i32, u32, i64, u64, f32, f64)
let mut timestamps: Vec<i64> = vec![1_760_000_005_000, 1_760_000_001_000, 1_760_000_003_000];
timestamps.lattice_sort();
assert!(timestamps.is_sorted());
let mut readings: Vec<f64> = vec![3.5, -0.0, 0.0, -12.8, 1.25];
readings.lattice_sort();
// 2. Multi-core parallel sorting for large i32 batches
let mut batch: Vec<i32> = (0..1_000_000).rev().collect();
parallel_lattice_sort(&mut batch);
assert!(batch.is_sorted());
}Reproducing the Benchmarks via CLI (Command-Line Interface, text-based terminal interface for running programs)
# Primary 1,000,000-element benchmark suite (9 distributions)
cargo bench --bench latticesort
# Comparison against 6 sorting algorithms from Computer Science literature
cargo bench --bench bench_literature
# Red-team adversarial falsification suite (1,000,000 elements)
cargo bench --bench adversarial
# 10x scale benchmark + red-team suite (10,000,000 elements)
cargo bench --bench bench_10m
# Polymorphic types (u32, i64, u64, f32, f64) and multi-core parallel benchmark
cargo bench --bench bench_fronts_3_4
# 1-Billion-element (4.00 GB) uniform 32-bit random benchmark
cargo bench --bench bench_1bAn interactive 3D WebGL visualizer of the internal stages of Lattice Sort is included in viz/index.html. Serve the repository root with any local static server to explore the 3D scene in your browser.
Released under the MIT (Massachusetts Institute of Technology, permissive free software license) License. Copyright (c) 2026 Robson Cassiano.
Author: Robson Cassiano (ORCID (Open Researcher and Contributor ID, persistent digital identifier for researchers): 0009-0009-5188-361X).
For the source code, cite the software entry below. GitHub's "Cite this repository" button reads CITATION.cff.
@software{cassiano2026latticesort,
author = {Cassiano, Robson},
title = {{Lattice Sort (latticesort)}: adaptive structural, hash-aggregated, and cache-aware hybrid radix sorting in safe Rust},
year = {2026},
version = {0.1.0},
url = {https://github.com/SimpleSoftwareLTDA/latticesort},
license = {MIT},
note = {Author ORCID: https://orcid.org/0009-0009-5188-361X}
}