Comprehensive Empirical Benchmarking of Twelve Sorting Algorithms Across Comparison-Based, Non-Comparison-Based, and Hybrid Paradigms: A Multi-Dimensional Performance Model for Algorithm Selection at Practical Data Scales (n up to 100,000)

This study extends the five-algorithm benchmark of Wibowo and Faisal [12] — which compared Heap, Shell, Merge, and Quick Sort against Python's built-in Timsort — to a twelve-algorithm framework spanning comparison-based, non-comparison-based, and hybrid/adaptive paradigms. Execution time (time.perf_counter()) and peak memory (tracemalloc) were measured across data sizes from 100 to 100,000 elements under random, ascending, and descending distributions, with stability and adaptivity empirically verified rather than only theoretically asserted. Results show that Counting Sort empirically breaks the Ω(n log n) comparison-sort lower bound under bounded key-range conditions, completing in 39.29 ms at n=100,000 versus 1,607.65–14,818.08 ms for the comparison-based algorithms tested (Mann-Whitney U test, p < 0.001). A key-range scaling experiment locates this advantage's precise boundary: it holds while the value range k remains at or below roughly 10 times n and inverts once k approaches 100 times n. Tim Sort remained the fastest overall algorithm (14.12 ms), while Bucket Sort's performance proved highly sensitive to its assumed value-range parameter, degrading toward quadratic behavior when that assumption diverged from the actual data range. All theoretical stability classifications were empirically confirmed, and a systematic rank-correlation analysis shows distribution sensitivity concentrated in adaptive algorithms' response to best-case ordering (ρ = 0.11–0.71 between random and ascending rankings) rather than in uniform reshuffling under any non-random input (ρ = 0.90–0.95 between random and descending rankings). The study contributes a reproducible, rule-based, multi-dimensional (time-space-stability-adaptivity) decision-support framework, presented as a decision-tree and rule table and checked, where independent data permits, against a held-out supplementary dataset, for algorithm selection at the moderate-to-large data scales tested here (n up to 100,000).

Sorting Algorithms, Timsort, Non-Comparison Sorting, Empirical Algorithmics, Algorithm Selection

1. Alkharabsheh, K., Alturani, I., Alturani, A., & Zanoon, N. (2013). Review on sorting algorithms: A comparative study. International Journal of Computer Science and Security, 7(3), 120–126. [Google Scholar] [Crossref]

2. Auger, N., Jugé, V., Nicaud, C., & Pivoteau, C. (2018). On the worst-case complexity of TimSort. In 26th Annual European Symposium on Algorithms (ESA 2018). https://doi.org/10.48550/arXiv.1805.08612 [Google Scholar] [Crossref]

3. Balasubramanian, S. A. (2025). Adaptive hybrid sort: Dynamic strategy selection for optimal sorting across diverse data distributions. arXiv. https://doi.org/10.48550/arXiv.2506.20677 [Google Scholar] [Crossref]

4. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms (3rd ed.). MIT Press. [Google Scholar] [Crossref]

5. Goel, K., Dwivedi, P., & Sharma, O. (2023). Performance analysis of various sorting algorithms: Comparison and optimization. 2023 11th International Conference on Intelligent Systems and Embedded Design (ISED), 1–5. https://doi.org/10.1109/ISED59382.2023.10444609 [Google Scholar] [Crossref]

6. Golonka, J., & Krużel, F. (2026). Empirical evaluation of unoptimized sorting algorithms on 8-bit AVR Arduino microcontrollers. Sensors, 26(1), 214. https://doi.org/10.3390/s26010214 [Google Scholar] [Crossref]

7. Oladipupo, E. T., Abikoye, O. C., Akande, N. O., Kayode, A. A., & Adeniyi, J. K. (2020). Comparative study of two divide and conquer sorting algorithms: Quicksort and mergesort. Procedia Computer Science, 171, 2532–2540. https://doi.org/10.1016/j.procs.2020.04.274 [Google Scholar] [Crossref]

8. Peters, T. (2002). listsort.txt. CPython git repository. https://svn.python.org/projects/python/trunk/Objects/listsort.txt [Google Scholar] [Crossref]

9. Romano, J., Kromrey, J. D., Coraggio, J., & Skowronek, J. (2006). Appropriate statistics for ordinal level data: Should we really be using t-test and Cohen's d for evaluating group differences on the NSSE and other surveys? Annual Meeting of the Florida Association of Institutional Research. [Google Scholar] [Crossref]

10. Sarwar, S. M., Jaragh, M. H. A., & Wind, M. (1994). An empirical study of the run-time behavior of quicksort, Shellsort and mergesort for medium to large size data. Computer Languages, 20(2), 127–134. https://doi.org/10.1016/0096-0551(94)90019-1 [Google Scholar] [Crossref]

11. Sundaramoorthy, S., & Karunanidhi, G. (2025). A systematic analysis on performance and computational complexity of sorting algorithms. Discover Computing. https://doi.org/10.1007/s10791-025-09724-w [Google Scholar] [Crossref]

12. Wibowo, F. R., & Faisal, M. (2024). Comparative analysis of sorting algorithms: TimSort Python and classical sorting methods. JISA (Jurnal Informatika dan Sains), 7(1), 11–18. [Google Scholar] [Crossref]

• Explainable 3D Convolutional Neural Networks Spatiotemporal Learning for Human Handshake Interaction Recognition