Answers are grounded in this paper and cite their sources.
This repository and replication package contains the full 30-page research manuscript, native Rust source code implementations, empirical benchmark harness, and Linux PMU hardware performance counter datasets evaluating 15 sorting algorithms across 5 input magnitudes (10² to 10⁶ elements) and 6 distinct data distribution patterns. Evaluated Algorithms Custom Implementations: Bubble Sort (early-exit flag), Selection Sort, Insertion Sort, Shell Sort (extended Ciura sequence), Merge Sort (preallocated scratch reuse), Quick Sort (median-of-3, Hoare partitioning, tail-call bounding), Heap Sort (Floyd binary max-heap), Tree Sort (explicit BST with duplicate counts), Introsort (Musser hybrid), Timsort (Peters natural-run detection & stack invariants), Counting Sort (bounded histogram frequency counting), Radix Sort (8-pass LSD ping-pong with sign-bit XOR inversion), and Bucket Sort (128-bit safe range distribution). Standard Library Baselines: Rust slice::sort (Driftsort) and slice::sort_unstable (IPNSort). Key Empirical Findings Instruction-Parallel Sorting Networks: Rust's standard library sort_unstable() (IPNSort) achieves peak comparison-based throughput on uniform random data (12.64 ms at N = 1,000,000), driven by branchless instruction-parallel sorting networks yielding an IPC of 3.49 and a negligible 0.54% cache miss rate. Branch-Free Linear Scalability: 8-pass LSD Radix Sort demonstrates strict linear scaling (19.74 ms at N = 1,000,000) and an ideal 0.00% branch misprediction rate across signed 64-bit integers (i64), outperforming classical Merge Sort by 3.4×. Adaptive Run Detection: On presorted arrays, slice::sort (0.23 ms) and Timsort (0.36 ms at N = 1,000,000) achieve up to 80× speedups by collapsing monotonic runs in linear time. Cache Thrashing in Heap Sort: Non-contiguous parent-child pointer strides (2i+1, 2i+2) cause Heap Sort to incur a massive 31.65% cache miss rate on hardware counters. Archive Contents paper/research_paper_sorting_algorithms.pdf: Complete 30-page research manuscript. paper/paper.typ: Typst source code used to generate the manuscript. src/algorithms/: Safe Rust source code for all 15 sorting algorithms. src/bin/benchmark.rs: High-resolution monotonic timer & Linux PMU perf_event_open telemetry harness. tests/correctness_tests.rs: Automated correctness and boundary validation test suite. results/: Raw empirical CSV records (2,849 trials), summary statistics, and hardware counter data. plots/: 13 SVG algorithm architecture diagrams and 6 publication benchmark charts (PDF/SVG). Reproduction Instructions # 1. Run automated correctness tests cargo test -- --nocapture # 2. Run release benchmark harness & collect PMU counters cargo run --release --bin benchmark # 3. Regenerate publication charts and architecture diagrams python3 src/generate_plots.py python3 src/generate_all_13_diagrams.py # 4. Recompile paper manuscript typst compile --root . paper/paper.typ paper/research_paper_sorting_algorithms.pdf
No takes yet. Share an insight, caveat, or question.
aditya prasad (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: