learned-partition-sort

A distribution-based sorting algorithm that achieves O(N) complexity by calculating element positions directly, bypassing comparison overhead.

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

Installation

[dependencies]

learned-partition-sort = "0.1"

Usage

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

Sample — Scan to find min/max bounds
Count — Bucket elements via linear interpolation
Scatter — Write to auxiliary buffer in calculated positions
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

Scenario	Recommendation
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

learned-partition-sort 0.1.0