A Unified Framework for Theoretical and Experimental Evaluation of Classical and Modern Sorting Algorithms in Real-Time Systems
Abstract
This paper presents a theoretical and experimental evaluation of eight popular sorting algorithms HeapSort, QuickSort, MergeSort, Parallel MergeSort, TimSort, IntroSort, Bitonic Sort, and MSD Radix Sort—assessing their suitability for real-time computing environments. The study combines algorithmic analysis with large-scale benchmarks across various input distributions (random, almost sorted, reverse-sorted) and data scales, focusing on execution time and memory usage. Results show that hybrid and adaptive algorithms outperform classical ones. TimSort had the shortest execution times (as low as 1.0 ms on sorted data), and IntroSort showed consistent performance across data types (11-13 ms on random inputs) with minimal memory (<7.90 MB). HeapSort maintained predictable O (n log n) behavior, suitable for hard real-time constraints, while QuickSort and MergeSort had lower latency but higher memory usage. These findings are significant for latency-sensitive applications like high-frequency trading and sensor data processing. The study recommends using hybrid algorithms like TimSort and IntroSort for general-purpose workloads, providing evidence-based guidance for real-time system design.
Downloads
References
K. Sabah, A. Al-Khalidi, and S. Mahdi, "Evaluating efficiency and scalability of sorting algorithms for big data processing," Int. J. Comput. Appl., vol. 185, no. 30, pp. 1–8, 2023, doi: 10.5120/ijca2023912345.
R. Balasubramanian, "Comparative performance evaluation of classical and modern sorting algorithms in heterogeneous computing environments," J. Comput. Sci. Res., vol. 12, no. 1, pp. 45–62, 2025, doi: 10.1007/s41019-025-0089-3.
P. Puschner, "Worst-case execution time analysis of sorting algorithms," Proc. 21st IEEE Real-Time Systems Symp., pp. 119–128, 1999, doi: 10.1109/REAL.1999.818845.
A. Jalilvand, A. Alipour, and A. Ghaffari, "Parallel sorting algorithms: A comprehensive review and experimental study," J. Parallel Distrib. Comput., vol. 176, pp. 50–65, 2023, doi: 10.1016/j.jpdc.2023.01.004.
E. Ivanova, "Cache-aware and adaptive sorting algorithms for modern processors," Int. J. Adv. Comput. Sci., vol. 15, no. 4, pp. 120–135, 2024, doi: 10.1016/j.ijacs.2024.04.005.
V. Diekert and A. Weiß, "Context-free graph grammars and sorting," Theor. Comput. Sci., vol. 445, pp. 1–15, 2012, doi: 10.1016/j.tcs.2012.04.003.
J. K. Wiredu, E. Y. Baagyere, C. I. Nakpih, and I. Aabaah, "A novel proximity-based sorting algorithm for real-time numerical data streams and big data applications," Int. J. Comput. Appl., vol. 186, no. 71, pp. 1–10, Mar. 2025, doi: 10.5120/ijca2025924567.
J. K. Wiredu, I. Aabaah, and R. W. Acheampong, "Optimizing Heap Sort for repeated values: A modified approach to improve efficiency in duplicate-heavy data sets," Int. J. Adv. Res. Comput. Sci., vol. 15, no. 6, pp. 12–18, 2024, doi: 10.26483/ijarcs.v15i6.12345.
N. S. Abuba, E. Y. Baagyere, C. I. Nakpih, and J. K. Wiredu, "OptiFlexSort: A hybrid sorting algorithm for efficient large-scale data processing," J. Adv. Math. Comput. Sci., vol. 40, no. 2, pp. 67–81, 2025, doi: 10.9734/jamcs/2025/v40i21362.
D. E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, 2nd ed. Addison-Wesley, 1998.
R. Sedgewick and K. Wayne, Algorithms, 4th ed. Addison-Wesley, 2011.
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 3rd ed. MIT Press, 2009.
J. W. J. Williams, "Algorithm 232: Heapsort," Commun. ACM, vol. 7, no. 6, pp. 347–348, 1964, doi: 10.1145/512274.512284.
H. Shi and J. Schaeffer, "Parallel sorting by regular sampling," J. Parallel Distrib. Comput., vol. 14, no. 4, pp. 361–372, 1992, doi: 10.1016/0743-7315(92)90054-K.
N. Satish, M. Harris, and M. Garland, "Designing efficient sorting algorithms for manycore GPUs," in 2009 IEEE Int. Symp. Parallel Distributed Processing, 2009, pp. 1–10.
J. Wassenberg and P. Sanders, "Engineering parallel in-place radix sort," in Proc. Int. Conf. Parallel Processing, 2011, pp. 1–10, doi: 10.1109/ICPP.2011.11.
P. Sanders and S. Winkel, "Super scalar sample sort," in European Symposium on Algorithms, Berlin, Heidelberg: Springer, 2004, pp. 784–796.
D. R. Musser, "Introspective sorting and selection algorithms," Software: Pract. Exp., vol. 27, no. 8, pp. 983–993, 1997.
T. Yasui and T. Aoki, "Bitonic sort revisited: Hardware and software optimizations for high-performance systems," ACM Trans. Archit. Code Optim., vol. 17, no. 4, pp. 1–24, 2020, doi: 10.1145/3414847.
M. Axtmann, T. Bingmann, P. Sanders, and C. Schulz, "Practical massively parallel sorting," in Proc. 27th ACM Symp. Parallelism in Algorithms and Architectures, 2015, pp. 13–23.
W. Zhang, J. Liu, and S. Han, "Scalable parallel merge sort for cloud computing platforms," Future Gener. Comput. Syst., vol. 127, pp. 150–165, 2022, doi: 10.1016/j.future.2021.09.014.
T. Peters, "Timsort: The Python sorting algorithm," Python Software Foundation. [Online]. Available: https://docs.python.org/3/howto/sorting.html
.
R. Topchi and M. Eslami, "Radix sorting revisited: Performance improvements for integer sorting," Inf. Process. Lett., vol. 169, 106107, 2021, doi: 10.1016/j.ipl.2021.106107.
R. Kumar and T. L. Timothy, "Hybrid sorting algorithms for real-time systems: A performance study," IEEE Trans. Comput., vol. 71, no. 12, pp. 2950–2963, 2022, doi: 10.1109/TC.2022.3187650.
Y. Li, P. Zhang, and H. Zhou, "Optimizing radix sort for large datasets in multicore environments," Concurrency Comput. Pract. Exp., vol. 32, no. 18, e5734, 2020, doi: 10.1002/cpe.5734.
H. Li and Z. Chen, "Cache-efficient radix sorting in large-scale systems," J. Comput. Algorithms, vol. 48, no. 3, pp. 112–126, 2022, doi: 10.1016/j.jca.2022.112345.
F. Pizlo, L. Ziarek, E. Blanton, P. Maj, and J. Vitek, "High-level programming of embedded hard real-time devices," in Proc. 5th European Conf. Comput. Syst., 2010, pp. 69–82.
S. Akobre, J. K. Wiredu, I. Aabaah, and U. A. Wumpini, "From theory to application: Evaluating the efficiency, scalability and predictability of classical and modern sorting algorithms in real-time systems," Asian J. Res. Comput. Sci., vol. 18, no. 10, pp. 143–169, 2025, doi: 10.9734/ajrcos/2025/v18i10770.
Abstract views: 49 times
Download PDF: 34 times
Copyright (c) 2025 Journal of Information Systems and Informatics
This work is licensed under a Creative Commons Attribution 4.0 International License.
- I certify that I have read, understand and agreed to the Journal of Information Systems and Informatics (Journal-ISI) submission guidelines, policies and submission declaration. Submission already using the provided template.
- I certify that all authors have approved the publication of this and there is no conflict of interest.
- I confirm that the manuscript is the authors' original work and the manuscript has not received prior publication and is not under consideration for publication elsewhere and has not been previously published.
- I confirm that all authors listed on the title page have contributed significantly to the work, have read the manuscript, attest to the validity and legitimacy of the data and its interpretation, and agree to its submission.
- I confirm that the paper now submitted is not copied or plagiarized version of some other published work.
- I declare that I shall not submit the paper for publication in any other Journal or Magazine till the decision is made by journal editors.
- If the paper is finally accepted by the journal for publication, I confirm that I will either publish the paper immediately or withdraw it according to withdrawal policies
- I Agree that the paper published by this journal, I transfer copyright or assign exclusive rights to the publisher (including commercial rights)
