bcsort 0.1.0

A fast, statistical, in-place ternary distribution sort.
Documentation

BCsort (Ben Chiboub Sort)

BCsort is a high-performance, in-place ternary distribution sorting algorithm engineered for Rust. Created by Hédi Ben Chiboub, it is designed to combat the Memory Wall by utilizing continuous-space spatial partitioning.

Instead of traditional median-pivot guessing (QuickSort) or bitwise bucketing (Radix Sort), BCsort calculates the spatial bounding box of the data and geometrically bisects it, routing elements into dynamically scaling "Gravity Wells."

Performance: The Radix Intercept

BCsort achieves its speed by maintaining a strict $O(1)$ auxiliary memory footprint. While memory-bound $O(N)$ sorts like radsort require massive $O(N)$ buffers, BCsort remains cache-resident, allowing it to outperform linear-time algorithms on datasets between $106$ and $108$ elements.

Hardware: i7-7900 | 24GB RAM
Environment: cargo run --release | RUSTFLAGS="-C target-cpu=native"
Data Type: f64 (Uniform Random Distribution)

SIZE SWEEP — Uniform random f64 — avg of 3 runs

N BCsort v2(s) Rayon par(s) radsort (s) vs Rayon vs radsort
1000 0.000230 0.000020 0.000015 BC -1053% BC -1429%
10000 0.000422 0.000172 0.000146 BC -146% BC -189%
100000 0.001506 0.000719 0.001686 BC -109% BC +12%
1000000 0.014371 0.007046 0.020077 BC -104% BC +40%
10000000 0.143960 0.063030 0.171723 BC -128% BC +19%
100000000 1.683463 0.891120 1.694845 BC -89% BC +1%

DISTRIBUTION STRESS — N = 1,000,000 — avg of 3 runs

Scenario BCsort v2(s) Rayon par(s) radsort (s) BC vs best
Uniform 0.014340 0.006156 0.031033 BC -133%
Gaussian 0.013630 0.005672 0.015943 BC -140%
Pareto (skewed) 0.013358 0.005585 0.015762 BC -139%
Nearly sorted 0.004368 0.003366 0.015141 BC -30%
5% NaN 0.013518 0.005486 0.016010 BC -146%

10M VARIANCE REPORT — 5 individual runs, uniform f64

Run BCsort v2(s) Rayon par(s) radsort (s)
1 0.147147 0.085279 0.174830
2 0.149357 0.085369 0.174691
3 0.151786 0.080296 0.173559
4 0.146650 0.079965 0.179120
5 0.148543 0.079260 0.177187

Architecture: 1D Octree Partitioning

BCsort treats sorting as a spatial subdivision problem rather than a comparison problem:

  1. Root Stats: A single parallel scan identifies the absolute min, max, and mean to anchor the data's center of gravity.
  2. Zero-Scan Recursion: After the root pass, BCsort uses Theoretical Bisection. Child chunks inherit their bounding boxes mathematically ($T_1 = \frac{min+mean}{2}$, $T_2 = \frac{mean+max}{2}$). This eliminates subsequent $O(N)$ stats scans, cutting memory bandwidth usage by ~50%.
  3. Cache-Aware DNF: Using an in-place 3-way Dutch National Flag partition, BCsort groups data into territories that remain resident in L2/L3 cache, bypassing the RAM latency of out-of-place distribution sorts.
  4. A mandatory $O(N)$ quarantine pass handles NaN and Inf values using total_cmp logic, ensuring zero-panic execution on scientific or sensor telemetry data.

👤 Author

Hédi Ben Chiboub Systems Architect & Pragmatic Engineer Portfolio

⚖️ License

Distributed under the MIT License. See LICENSE for more information.