Distribution of Execution Times for Sorting Algorithms Implemented in Java

Kirby McMaster, Samuel Sambasivam, Brian Rague, Stuart Wolthuis
InSITE 2015  •  2015  •  pp. 269-283
Algorithm performance coverage in textbooks emphasizes patterns of growth in execution times, relative to the size of the problem. Variability in execution times for a given problem size is usually ignored. In this research study, our primary focus is on the empirical distribution of execution times for a given algorithm and problem size. We examine CPU times for Java implementations of five sorting algorithms for arrays: selection sort, insertion sort, shell sort, merge sort, and quicksort. We measure variation in running times for these algorithms and describe how the sort-time distributions change as the problem size increases. Using our research methodology, we compare the relative stability of performance for the different sorting algorithms.
algorithm, sorting, performance, distribution, variation, Java
102 total downloads
Share this

Back to Top ↑