Faster deterministic sorting and priority queues in linear space
Mikkel Thorup · MPG.PuRe (Max Planck Society) · 1998
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.