Integer Sorting in 0(n\sqrt {\log \log n}) Expected Time and Linear Space

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.