Abstract

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.

References

• M. Dietzfelbinger, T. Hagerup, J. Katajainen, M. Penttonen, A reliable randomized algorithm for the closest-pair problem, J. Algorithms 25, 1997.
• M. Thorup, Randomized sorting in O(n log log n) time and linear space using addition, shift, and bit-wise boolean operations, in: Proc. 8th ACM–SIAM Symposium on Discrete Algorithms (SODA’97), 1997.
• Y. Han, M. Thorup, Sorting integers in O(n √(log⁡log⁡n )) expected time and linear space, IEEE Symposium on Foundations of Computer Science (FOCS’02), 2002.
• A. Andersson, T. Hagerup, S. Nilsson, R. Raman, Sorting in linear time?, Symposium on Theory of Computing, 1995.
• Y. Han, X. Shen, Conservative algorithms for parallel and sequential integer sorting, International Computing and Combinatorics Conference, 1995.
• Y. Han, Deterministic sorting in O(n log log n) time and linear space, 34th STOC, 2002.
• P. van Emde Boas, R. Kaas, E. Zijlstra, Design and implementation of an efficient priority queue, Math. Syst. Theory 10, 1977.
• A. Andersson, Fast deterministic sorting and searching in linear space, IEEE Symposium on Foundations of Computer Science, 1996.
• Y. Han, Improved fast integer sorting in linear space, Inform. and Comput., 2001.
• T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein: Introduction to Algorithms, Second Edition,The MIT Press and McGraw-Hill Book Company, 2001.
• S. Albers, T. Hagerup, Improved parallel integer sorting without concurrent writing, Inform. and Comput., 1997.
• M.L. Fredman, D.E. Willard, Surpassing the information theoretic bound with fusion trees, J. Comput. System Sci., 1994.
• T. Hagerup, H. Shen, Improved nonconservative sequential and parallel integer sorting, Inform. Process. Lett., 1990.
• D. Kirkpatrick, S. Reisch, Upper bounds for sorting integers on random access machines, Theoret. Comput. Sci., 1984.
• R. Raman, Priority queues: small, monotone and trans-dichotomous, European Symp. on Algorithms, 1996.
• M. Thorup, Fast deterministic sorting and priority queues in linear space, ACM–SIAM Symp. on Discrete Algorithms (SODA’98), 1998.