Абстрактный

IMPROVING PERFORMANCE OF RANDOMIZED SIGNATURE SORT USING HASHING AND BITWISE OPERATORS

Tamana Pathak and Dr. Deepak Garg

Research done in the area of integer sorting has considerably improved the lower bound and achieved with comparison sorting i.e. to [1] for a deterministic algorithms or to 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 traditional quick sort. It is well known that integers in the range [1, c] can be sorted in time using radix sorting. Integers in any range [1, ] can be sorted in time [1]. However, these algorithms use words of extra memory. We present a simple and stable variant of signature sort for integer sorting, which works in time and uses only words of extra memory. In this we are trying to improve the performance of the signature sort by implementing differently and comparing its performance against traditional sorting algorithms and to see the effect of register size on the algorithm.