Implementation and Performance Analysis of Exponential Tree Sorting
Ajit Singh, Deepak Garg · International Journal of Computer Applications · 2011
The traditional algorithm for sorting gives a bound of expected time without randomization and with randomization.Recent researches have optimized lower bound for deterministic algorithms for integer sorting [1][2][3].Andersson has given the idea of Exponential tree which can be used for sorting [4].Andersson, Hagerup, Nilson and Raman have given an algorithm which sorts n integers in expected time but uses space [4,5].Andersson has given improved algorithm which sort integers in expected time and linear space but uses randomization [2,4].Yijie Han has improved further to sort integers in expected time and linear space but passes integers in a batch i.e. all integers at a time [6].These algorithms are very complex to implement.In this paper we discussed a way to implement the exponential tree sorting and later compare results with traditional sorting technique.