The 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02) Integer Sorting in 0(n\sqrt {\log \log n}) Expected Time and Linear Space Vancouver, BC, Canada November 16-November 19 ISBN: 0-7695-1822-2
We present a randomized algorithm sorting n integers in 0(n\sqrt {\log \log n}) expected time and linear space. This improves the previous O(n log log n) bound by Anderson et al. from STOC?95. As an immediate consequence, if the integers are bounded by U, we can sort them in 0(n\sqrt {\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 from FOCS?75. 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 \sqrt n in linear time and space. This also implies improved bounds for deterministic string sorting and integer sorting without multiplication.
Citation:
Yijie Han, Mikkel Thorup, "Integer Sorting in 0(n\sqrt {\log \log n}) Expected Time and Linear Space," focs, pp.135, The 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02), 2002 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb