An incremental soting algorithm for arrays. When you know which values changed, DeltaSort restores order multi-fold faster than a full re-sort.
cd rust
cargo test # Run correctness tests
cargo benchmark # Run benchmarks
cargo benchmark-export # Run benchmarks and export data to diagramscd js
pnpm install
pnpm test
pnpm benchmark
pnpm benchmark:export| k | FullSort (µs) | BIS (µs) | DeltaSort (µs) | ESM (µs) |
|---|---|---|---|---|
| 1 (0.001%) | 1215.0 ±0.3% | 113.4 ±1.5% 🪶 | 15.7 ±4.3% ⚡ | 797.8 ±0.4% |
| 10 (0.01%) | 2012.6 ±0.5% | 1127.8 ±1.1% 🪶 | 98.2 ±3.0% ⚡ | 1006.8 ±0.6% |
| 100 (0.1%) | 4559.8 ±0.5% | 🐢 | 395.5 ±4.4% ⚡🪶 | 1195.7 ±0.5% |
| 1000 (1%) | 12065.1 ±0.4% | 🐢 | 1375.7 ±5.9% ⚡🪶 | 1426.2 ±1.0% |
| 10000 (10%) | 12577.8 ±0.2% | 🐢 | 6053.9 ±2.7% 🪶 | 3023.4 ±0.9% ⚡ |
| 20000 (20%) | 13507.6 ±0.3% | 🐢 | 10024.5 ±2.0% 🪶 | 4801.4 ±0.4% ⚡ |
| 50000 (50%) | 15421.2 ±0.6% | 🐢 | 🐢 | 10516.2 ±0.2% ⚡🪶 |
| 100000 (100%) | 16711.4 ±0.2% | 🐢 | 🐢 | 🐢 |
⚡ = Fastest 🪶 = Uses least memory 🐢 = too slow, FullSort is faster
Rust on Apple M-series. Results are environment-specific — JavaScript on V8 has a much lower crossover threshold.
- Phase 1: Extract updated values, sort them, write back to original indices.
- Phase 2: Fix each violation using binary insertion on a constrained range.
The key insight: pre-sorting dirty values creates segments that can be fixed locally and independently. See the paper for formal proofs.
paper/ — LaTeX source for the paper
rust/ — Rust implementation + benchmarks
js/ — JavaScript implementation + benchmarks
This is early-stage. If you:
- Find bugs or edge cases
- Have suggestions for the paper
- Want to discuss applications
Please open an issue or reach out!
MIT