(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
O(min(
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.
sqrt(log n)
log n/log w + loglog n
log w loglog n
))