Ten common sorting algorithms were implemented and executed on a computer with Intel Pentium-4 running the Microsoft Windows XP operating system. Best case and worst case analyses of the algorithms were performed for lists of 1,000 to 10,000 integers. An improved version of bubble sort algorithm and the recursive quick sort algorithm were the fastest in the best case and the worst case, respectively. Equations for the execution times were also extracted from this analysis. The results displayed the actual performance of the algorithms on the given platform.

The results of this study can be used to predict the execution time of these algorithms for an input of arbitrary size. Moreover, the results can be used to compare the performances of new sorting algorithms with those of the existing ones. The study also shows that an algorithm whose execution time is bound by a loose asymptotic limit may run faster than an algorithm whose execution time is bound by a stricter asymptotic limit. This signifies the need to study the actual execution times of algorithms on different hardware and software platforms.

Algorithms, like computer hardware, are a technology. The total system performance depends on choosing efficient algorithms as much as on choosing fast hardware. Just as rapid advances are being made in other computer technologies, they are being made in algorithms as well (Cormen et al., 2001). Sorting is one of the most important and well-studied problems in computer science (Biggar et al., 2008). Today, a large number of sorting algorithms are in use. Although the behaviors of these algorithms have been studied theoretically by calculating their time complexities, not much work has been done to test how these algorithms perform practically on different machines using different hardware and software platforms. As a result, the need of such empirical researches on sorting algorithms has been felt recently (Biggar et al., 2008).

The performance of an algorithm on a particular system depends on a large number of issues like processor speed, size of cache memory, size of primary memory, etc. Hence, in a practical situation the performance of an algorithm may differ from the theoretical predictions. To determine the most suitable sorting algorithm for a particular application, it is necessary to consider each sorting algorithm in the light of the requirements of the application, the nature of the data being sorted and the characteristics of the hardware and the software platforms to be used (Hall, 1963). These factors may even disqualify some sorting algorithms due to time and/or space limitations.

The best, and perhaps the only, way to measure the actual performance of any algorithm is to implement and run it, collect actual execution times, and extract equations for the execution times (Sarwar et al., 1996). This paper uses this theory and aims to study the execution times of some widely used sorting algorithms on a familiar platform.

Computer Sciences Journal, Sorting Algorithms, Software Platforms, Computer Technologies, Bubble Sort, Merge Sort Algorithms, Quick Sort Algorithms, Computer Algorithms, Data Structures, Hardware Platforms, Selection Sort.