Multiple Pivot Sort Algorithm is Faster than Quick Sort Algorithms: An Empirical Study
Salman Faiz Solehria, Sultanullah Jadoon · 2011
Multiple Pivot Sort is a new comparison- based sorting algorithm that has been developed to address shortcomings in current popular comparison-based sorting algorithms. The goal of this work is to perform an extensive empirical study of Multiple Pivot Sort against other established sorting algorithms including Quick Sort, Merge Sort, and Heap Sort. This research presents data to support the hypothesis that Multiple Pivot Sort is an extremely promising new algorithm in a critical field of Computer Science. The empirical study includes comparisons of the various sorts using randomly generated arrays of size 10 data items up to 1 million or more data items. In addition, integer arrays in which the data is in order and in reverse order are used in the study. Data items include integers, strings, and classes. The study keeps track of the number of comparisons, the number of data moves, and CPU time specific to the machine for each sort. Results of the empirical study performed in this research support the claim that Multiple Pivot Sort may well be the fastest sorting algorithm in existence.