Implementation and Performance Analysis of Exponential Tree Sorting

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-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. General Terms Algorithms, Data Structure.