Anzeige
Erschienen in:
2014 | OriginalPaper | Buchkapitel
Expected Linear Time Sorting for Word Size Ω(log2 n loglogn)
verfasst von : Djamal Belazzougui, Gerth Stølting Brodal, Jesper Sindahl Nielsen
Erschienen in: Algorithm Theory – SWAT 2014
Verlag: Springer International Publishing
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Sorting
n
integers in the word-RAM model is a fundamental problem and a long-standing open problem is whether integer sorting is possible in linear time when the word size is
ω
(log
n
). In this paper we give an algorithm for sorting integers in expected linear time when the word size is Ω(log
2
n
loglog
n
). Previously expected linear time sorting was only possible for word size Ω(log
2 +
ε
n
). Part of our construction is a new packed sorting algorithm that sorts
n
integers of
w
/
b
-bits packed in
${\mathcal O}(n/b)$
words, where
b
is the number of integers packed in a word of size
w
bits. The packed sorting algorithm runs in expected
${\mathcal O}(\tfrac{n}{b}(\log n + \log^2 b))$
time.