Published Articles >> Table of Contents >> Abstract

The 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02)   p. 135
Integer Sorting in 0(n\sqrt {\log \log n}) Expected Time and Linear Space
Yijie Han, University of Missouri at Kansas City
Mikkel Thorup, AT&T Labs - Research Shannon Laboratory

Full Article Text:

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/SFCS.2002.1181890
Send link to a friend

Abstract
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.
Back to Top Additional Information
Citation:  Yijie Han, Mikkel Thorup, "Integer Sorting in 0(n\sqrt {\log \log n}) Expected Time and Linear Space," focs, p. 135,  The 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02),  2002