Distribution of Execution Times for Sorting Algorithms Implemented in Java

Citations Over Time

Abstract

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.

Related Papers

• → Performance Evaluation of Parallel Sorting Algorithms on IMAN1 Supercomputer(2016)17 cited
• → Distribution of Execution Times for Sorting Algorithms Implemented in Java(2015)2 cited
• → Timing results of some internal sorting algorithms on vector computers(1987)10 cited
• → Advanced Sorting Algorithms(2007)
• → Performance Analysis of QuickMerge and QuickInsertionMerge Algorithms(2023)