International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
|
Volume 24 - Issue 3 |
Published: June 2011 |
Authors: Ajit Singh, Dr. Deepak Garg |
![]() |
Ajit Singh, Dr. Deepak Garg . Implementation and Performance Analysis of Exponential Tree Sorting. International Journal of Computer Applications. 24, 3 (June 2011), 34-38. DOI=10.5120/2929-3876
@article{ 10.5120/2929-3876, author = { Ajit Singh,Dr. Deepak Garg }, title = { Implementation and Performance Analysis of Exponential Tree Sorting }, journal = { International Journal of Computer Applications }, year = { 2011 }, volume = { 24 }, number = { 3 }, pages = { 34-38 }, doi = { 10.5120/2929-3876 }, publisher = { Foundation of Computer Science (FCS), NY, USA } }
%0 Journal Article %D 2011 %A Ajit Singh %A Dr. Deepak Garg %T Implementation and Performance Analysis of Exponential Tree Sorting%T %J International Journal of Computer Applications %V 24 %N 3 %P 34-38 %R 10.5120/2929-3876 %I Foundation of Computer Science (FCS), NY, USA
The traditional algorithm for sorting gives a bound of O(n log n) expected time without randomization and O(n) 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 O(n log log n) expected time but uses O(mᵋ) space [4, 5]. Andersson has given improved algorithm which sort n integers in O(n log log n) expected time and linear space but uses randomization [2, 4]. Yijie Han has improved further to sort n integers in O(n log log n) 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.