learned-partition-sort

Crates.iolearned-partition-sort
lib.rslearned-partition-sort
version0.1.0
created_at2026-01-08 06:51:25.621299+00
updated_at2026-01-08 06:51:25.621299+00
descriptionA high-performance distribution-based sorting algorithm that learns data patterns to achieve O(N) complexity
homepage
repositoryhttps://github.com/keeth/learned-partition-sort
max_upload_size
id2029671
size55,713
Keethesh Mootoosamy (keethesh)

documentation

README

learned-partition-sort

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

CI Crates.io License: MIT Rust

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

  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

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

Commit count: 0

cargo fmt