Improved Exponential Tree Integer Sorting Algorithm Using Node Growth

Abstract

The traditional algorithm for integer sorting gives a lower bound ofO(n log n) expected time without randomization andO(n) with randomization. Recent researches have optimized lower bound for deterministic algorithms for integer sorting. This thesis will present an idea to achieve the complexity of deterministic algorithm for integer sorting in O(n log log n log log logn) expected time and linear space which is easy to implement and very simple enough. The idea will use Andersson’s exponential tree to perform the sorting. The exponential tree can’t be used as it is for this idea, so the modification in the exponential tree is necessary. Integers will be passed down to exponential tree one at a time but limit the comparison required at each level. The total number of comparison for any integer will beO(log logn log log n) i.e. total time taken for all integers insertion will beO(n log log nlog log n) . The algorithm presented in this thesis can be compared with the result of Fredman and Willard that sorts n integers ino(nlogn/log logn) time in linear space. It can also be compared with result of Raman that sorts n integers inO(nlog nlog log n) time in linear space and also with result of Andersson’s time bound ofO(nlog n) . The algorithm can also be compared with Yijei Han’s result ofO(nlog logn log log log n) expected time for deterministic linear space integer sorting. The implementation of the algorithm is also given and later performance is compared to traditional deterministic algorithms.