Comparative Evaluation and Architectural Analysis of Sorting Algorithms in Modern C++

Sorting remains a foundational operation in systems software, database kernels, and runtime libraries. While theoretical asymptotic bounds (O(N²), O(N log N), and O(N)) are well established, real-world execution times on modern superscalar architectures diverge substantially due to cache hierarchy latencies, hardware branch mispredictions, and input distributions. This paper presents a controlled, reproducible empirical evaluation of fifteen sorting algorithms implemented in C++17: Bubble, Selection, Insertion, Shell, Merge, Quick, Heap, Tree, Intro, Tim, Counting, Radix (LSD), and Bucket Sort, alongside practical baselines std::sort and std::stable_sort. Benchmarks were executed on an Intel 12th Gen Core i7-12700F processor running CachyOS Linux across input scales from 10² to 10⁶ elements under six distinct distributional regimes: uniform random, strictly sorted, reverse sorted, nearly sorted (1% perturbations), heavy duplicates (10 distinct keys), and small-range integers ([0, 1000]). Using Linux perf_event_open hardware monitoring, we measure CPU cycles, cache references, cache misses, branch instructions, and branch mispredictions. The experimental data confirms that non-comparison Radix Sort achieves the highest throughput on random 32-bit keys (5.67 ms at N=10⁶) with a negligible 0.00055% branch misprediction rate, while Timsort demonstrates unmatched adaptivity on presorted inputs (0.266 ms at N=10⁶) consuming only 1.82 million CPU cycles. Unbalanced Tree Sort exhibits catastrophic latency inflation on duplicate inputs (2119.55 ms vs. 12.42 ms at N=10⁵) requiring 9.48 billion CPU cycles due to extreme right-skew. We synthesize these empirical and hardware measurements into a practical selection matrix for systems software engineering.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-15
DOI
https://doi.org/10.5281/zenodo.24248768
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 Evaluation and Architectural Analysis of Sorting Algorithms in Modern C++

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

Comparative Evaluation and Architectural Analysis of Sorting Algorithms in Modern C++

aditya prasad
preprint en

Abstract

Sorting remains a foundational operation in systems software, database kernels, and runtime libraries. While theoretical asymptotic bounds (O(N²), O(N log N), and O(N)) are well established, real-world execution times on modern superscalar architectures diverge substantially due to cache hierarchy latencies, hardware branch mispredictions, and input distributions. This paper presents a controlled, reproducible empirical evaluation of fifteen sorting algorithms implemented in C++17: Bubble, Selection, Insertion, Shell, Merge, Quick, Heap, Tree, Intro, Tim, Counting, Radix (LSD), and Bucket Sort, alongside practical baselines std::sort and std::stable_sort. Benchmarks were executed on an Intel 12th Gen Core i7-12700F processor running CachyOS Linux across input scales from 10² to 10⁶ elements under six distinct distributional regimes: uniform random, strictly sorted, reverse sorted, nearly sorted (1% perturbations), heavy duplicates (10 distinct keys), and small-range integers ([0, 1000]). Using Linux perf_event_open hardware monitoring, we measure CPU cycles, cache references, cache misses, branch instructions, and branch mispredictions. The experimental data confirms that non-comparison Radix Sort achieves the highest throughput on random 32-bit keys (5.67 ms at N=10⁶) with a negligible 0.00055% branch misprediction rate, while Timsort demonstrates unmatched adaptivity on presorted inputs (0.266 ms at N=10⁶) consuming only 1.82 million CPU cycles. Unbalanced Tree Sort exhibits catastrophic latency inflation on duplicate inputs (2119.55 ms vs. 12.42 ms at N=10⁵) requiring 9.48 billion CPU cycles due to extreme right-skew. We synthesize these empirical and hardware measurements into a practical selection matrix for systems software engineering.

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
Comparative Evaluation and Architectural Analysis of Sorting Algorithms in Modern C++ — aditya prasad · Zenodo (CERN European Organization for Nuclear Research) (2026) | TGRS Research Map | TGRS