Integer sorting in O(n√(log log n)) expected time and linear space
Yijie Han, Mikkel Thorup · 2003
We present a randomized algorithm sorting n integers in O(n/spl radic/(log log n)) expected time and linear space. This improves the previous O(n log log n) bound by Anderson et al. (1995). As an immediate consequence, if the integers are bounded by U, we can sort them in O(n/spl radic/(log log U)) expected time. This is the first improvement over the O (n log log U) bound obtained with van Emde Boas' data structure. At the heart of our construction, is a technical deterministic lemma of independent interest; namely, that we split n integers into subsets of size at most /spl radic/n in linear time and space. This also implies improved bounds for deterministic string sorting and integer sorting without multiplication.