From Theory to Application: Evaluating the Efficiency, Scalability and Predictability of Classical and Modern Sorting Algorithms in Real-Time Systems

Abstract

Efficient and predictable sorting is critical for real-time computing applications, including embedded systems, financial trading platforms, and sensor networks. In this paper, a strict comparative analysis of five popular sorting algorithms, namely Heap Sort, Merge Sort, Quick Sort, Tim Sort, and Intro Sort, in different input situations, i.e., almost sorted, random, and reverse-sorted data, is provided. Every algorithm was tested using 30 independent trials per condition so that the statistical strength is attained. Findings have shown that Tim Sort has a consistently better performance, the lowest execution time (6 ms) and the smallest memory footprint (7.80 MB), and thus its flexibility to data patterns of various types. Quick Sort is fast in cases that are average-case but has a higher memory overhead in cases where the input is reversed sorting. Hack Sort is stable with random data and Quick Sort is fast with average-case data. Merge Sort is predictable but resource-intensive, as the execution time goes up to 28 ms, and memory consumption is up to 8.34 MB. The performance of Intro Sort is balanced and has execution time of 11-13 ms and a memory size of less than 7.90 MB, regardless of the dataset. The significance of these differences can be proved by statistical procedures and correlations such as one-way ANOVA and post-hoc tests (Tukey) with the significance level of p less than 0.001. The combination of empirical assessment with strong statistical verification makes this study offer practical advice on the choice of algorithms in the latency sensitive computing environment. Further studies will elaborate this framework to parallel and distributed versions, which allows scalable and high performance sorting in the present-day real-time systems.