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
- aditya prasad (ORCID: https://orcid.org/0009-0004-4853-1932)
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