Comparative Performance Evaluation and Architectural Analysis of Sorting Algorithms in Rust

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 Correspondence & Contact: [email protected]

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-16
DOI
https://doi.org/10.5281/zenodo.24280052
Primary Topic
Parallel Computing and Optimization Techniques
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Comparative Performance Evaluation and Architectural Analysis of Sorting Algorithms in Rust

aditya prasad
1 links
Zenodo (CERN European Organization for Nuclear Research)
Parallel Computing and Optimization Techniques
preprint

Comparative Performance Evaluation and Architectural Analysis of Sorting Algorithms in Rust

aditya prasad
preprint en

Abstract

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 Correspondence & Contact: [email protected]

Zenodo (CERN European Organization for Nuclear Research)
Parallel Computing and Optimization Techniques
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon