@techreport{Mikkel97,
TITLE = {Faster deterministic sorting and priority queues in linear space},
AUTHOR = {Thorup, Mikkel},
LANGUAGE = {eng},
NUMBER = {MPI-I-1997-1-016},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
ADDRESS = {Saarbr{\"u}cken},
YEAR = {1997},
DATE = {1997},
ABSTRACT = {The RAM complexity of deterministic linear space sorting of integers in words is improved from $O(n\sqrt{\log n})$ to $O(n(\log\log n)^2)$. No better bounds are known for polynomial space. In fact, the techniques give a deterministic linear space priority queue supporting insert and delete in $O((\log\log n)^2)$ amortized time and find-min in constant time. The priority queue can be implemented using addition, shift, and bit-wise boolean operations.},
TYPE = {Research Report / Max-Planck-Institut für Informatik},
}