Parameterized Complexity of Quick Sort, Heap Sort and K-sort Algorithms with Quasi Binomial Input

Abstract

Parameterized complexity is one of the important concepts that has emerged in the recent past in the field of computer science. It has been observed that for certain algorithms such as sorting, the parameters of the input distribution characterizing the sorting elements are very crucial in explaining the complexity of an algorithm (see Anchala, Chakraborty (2007,2008), Chakraborty&Sourabh,(2007)).The present paper investigates the parameterized complexity of three sorting algorithms namely, Quick sort, Heap sort and K-sort ( with the same average case complexity O(Nlog2N)), for the quasi binomial input parameters and compares the results with those for binomial input parameters.