English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
  DetailsSummary

Released
Report

Faster deterministic sorting and priority queues in linear space

MPS-Authors
/persons/resource/persons45619

Thorup,  Mikkel
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

1997-1-016
(Any fulltext), 10KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Thorup, M.(1997). Faster deterministic sorting and priority queues in linear space (MPI-I-1997-1-016). Saarbrücken: Max-Planck-Institut für Informatik.


Cite as: https://hdl.handle.net/11858/00-001M-0000-0014-9D86-E
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.