Partition Sort versus Quick Sort: A Comparative Average Case Analysis with Special Emphasis on Parameterized Complexity

摘要

In our previous work we introduced Partition sort and found it to be more robust compared to the Quick sort in average case. This paper does a more comprehensive comparative study of the relative performance of these two algorithms with focus on parameterized complexity analysis. The empirical results revealed that Partition sort is the better choice for discrete distribution inputs, whereas Quick sort was found to have a clear edge for continuous data sets.