A. Andersson. Faster deterministic sorting and searching in linear space.
In Proc. 37th IEEE Symposium on Foundations of Computer Science, 1996.

(Mathematical expressions are simplified in this html-dokument. They should be readable enough to get the flavour.)

We present a significant improvement on linear space deterministic sorting and searching. On a unit-cost RAM with word size w, an ordered set of n w-bit keys (viewed as binary strings or integers) can be maintained in

sqrt(log n)
log n/log w + loglog n
log w loglog n

time per operation, including insert, delete, member search, and neighbour search. The cost for searching is worst-case while the cost for updates is amortized. % For range queries, there is an additional cost of reporting the found keys. As an application, n keys can be sorted in linear at O(n sqrt(log n)) worst-case cost.

The best previous method for deterministic sorting and searching in linear space has been the fusion trees which supports updates and queries in O(log n/loglog n) amortized time and sorting in O(n log n/loglog n) worst-case time.

We also make two minor observations on adapting our data structure to the input distribution and on the complexity of perfect hashing.

Full paper (postscript)
Full paper (pdf)