# learned-partition-sort
A distribution-based sorting algorithm that achieves O(N) complexity by calculating element positions directly, bypassing comparison overhead.
[]()
[]()
[](LICENSE)
[]()
---
## Benchmark Results
```
Throughput (Melem/s) — higher is better
┌──────────────────────────────────────────────┐
100K uniform │████████████████████████████████ 145 (+66%)
1M uniform │██████████████████████████ 90 (+32%)
10M uniform │█████████████████████ 62 (+29%)
└──────────────────────────────────────────────┘
vs slice::sort_unstable
```
Full results: [docs/BENCHMARKS.md](docs/BENCHMARKS.md)
---
## Installation
```toml
[dependencies]
learned-partition-sort = "0.1"
```
## Usage
```rust
use learned_partition_sort::learned_sort;
let mut data: Vec<i64> = vec![5, 2, 8, 1, 9, 3, 7, 4, 6];
learned_sort(&mut data);
assert_eq!(data, vec![1, 2, 3, 4, 5, 6, 7, 8, 9]);
```
---
## Algorithm
1. **Sample** — Scan to find min/max bounds
2. **Count** — Bucket elements via linear interpolation
3. **Scatter** — Write to auxiliary buffer in calculated positions
4. **Refine** — Parallel-sort buckets with Rayon
The algorithm assumes roughly uniform distribution. For adversarial inputs (all duplicates), it gracefully degrades to O(N log N).
---
## When to Use
| N ≥ 100K, numerical data | ✅ Use LPS |
| N < 32K | ⚠️ Falls back to `sort_unstable` automatically |
| Memory constrained | ❌ LPS requires O(N) auxiliary space |
| Non-numeric types | ❌ Use std sort |
---
## Limitations
- **Memory:** Requires O(N) auxiliary buffer
- **Types:** Only works with `Ord + Copy + Send + Sync` numeric types
- **Distribution:** Optimized for uniform/near-uniform distributions
- **Small N:** Overhead exceeds benefit below 32K elements (auto-fallback handles this)
---
## Acknowledgments
This project was built with significant assistance from AI coding assistants:
- **Gemini 3 Pro** (Google) — Original algorithm concept and high-level design
- **Claude Opus 4.5** (Anthropic) — Planning, implementation, debugging, and optimization
- **Google Antigravity** — Development workflow and rapid iteration
The project direction, architecture decisions, and performance validation were human-driven. The LLMs served as powerful pair-programming partners, dramatically accelerating development while the human maintained creative control.
---
## Contributing
Issues and PRs welcome. Please run `cargo test` and `cargo clippy` before submitting.
## License
MIT — see [LICENSE](LICENSE)