International Journal of Computer Applications |
Foundation of Computer Science (FCS), NY, USA |
Volume 23 - Number 6 |
Year of Publication: 2011 |
Authors: Tamana Pathak, Dr. Deepak Garg |
10.5120/2895-3787 |
Tamana Pathak, Dr. Deepak Garg . Article:Randomized Signature Sort: Implementation & Performance Analysis. International Journal of Computer Applications. 23, 6 ( June 2011), 1-5. DOI=10.5120/2895-3787
Recently the lower bound for integer sorting has considerably improved and achieved with comparison sorting O(n log n) to O (n√(loglogn )) [1] for a deterministic algorithms or to O(n) for a radix sort algorithm in space that depends only on the number of input integers. Andersson et al. [2] presented signature sort in the expected linear time and space which gives very bad performance than randomized quick sort. We earlier presented in [14] that performance of signature sort can be enhanced using hashing and bitwise operators. This paper gives the implementation of that idea and later we have compared the performance of algorithm with existing randomized signature sort and randomized quick Sort.