An incremental soting algorithm for arrays. When you know which values changed, DeltaSort restores order multi-fold faster than a full re-sort.
cd paper
make # Builds both article (paper/article.pdf) and SEA/LIPIcs version (paper/sea.pdf)
make clean # Remove build artifactsRequires a TeX Live installation with
pdflatexandbibtex.
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%) | 931.2 ±0.4% | 242.7 ±0.3% 🪶 | 12.2 ±3.3% ⚡ | 345.3 ±0.6% |
| 10 (0.01%) | 1574.1 ±0.6% | 684.2 ±0.8% 🪶 | 74.8 ±3.2% ⚡ | 566.4 ±0.4% |
| 100 (0.1%) | 3527.8 ±0.3% | 🐢 | 277.3 ±3.8% ⚡ | 702.2 ±0.1% |
| 1000 (1%) | 9181.7 ±0.1% | 🐢 | 818.9 ±3.8% ⚡ | 903.1 ±0.2% |
| 10000 (10%) | 9401.7 ±0.2% | 🐢 | 3617.7 ±3.5% | 2126.8 ±0.2% ⚡ |
| 20000 (20%) | 10187.1 ±0.3% | 🐢 | 5939.7 ±2.5% | 3498.4 ±0.3% ⚡ |
| 50000 (50%) | 11619.3 ±0.4% | 🐢 | 🐢 | 7777.3 ±1.0% ⚡ |
| 100000 (100%) | 12567.5 ±0.5% | 🐢 | 🐢 | 🐢 |
⚡ = Fastest 🪶 = Least memory (O(1) auxiliary) 🐢 = too slow, FullSort is faster
Rust on Apple M3 Pro. 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