Randomized sorting in O(n log log n) time and linear space using addition, shift, and bit-wise boolean operations
Mikkel Thorup · 1997
A randomized sorting algorithm is presented, doing as described in the title. 1 Introduction In this paper we consider sorting on a very simple RAM where the only word-operations are addition, shift, and bit-wise boolean operations. Besides these word-operations, we have direct and indirect addressing, jumps, and conditional statements. Such a RAM has been referred to as a Practical RAM [Mil96]. In this paper we show Theorem 1 On a Practical RAM, there is a randomized algorithm sorting n words in O(n log log n) time and linear space. The above algorithm only makes shifts by powers of two, and it only needs O(log n) random words. Our time bound matches that of the current fastest sorting algorithm by Andersson, Hagerup, Raman, and Nilsson [AHNR95]. Their algorithm has two variants: one is deterministic uses space 2 "w , where w is the word length and " is a positive constant. Thus the space is unbounded in terms of n. The other variant is randomized and uses linear space like ou...