Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review
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 log log n). Previously expected linear time sorting was only possible for word size Ω(log2+ε n). Part of our construction is a new packed sorting algorithm that sorts n integers of w/b-bits packed in 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 O(n/b(log n + log2 b)) time.
Original language | English |
---|---|
Title of host publication | Algorithm Theory – SWAT 2014 : 14th Scandinavian Symposium and Workshops, Copenhagen, Denmark, July 2-4, 2014. Proceedings |
Editors | R. Ravi, Inge Li Gørtz |
Number of pages | 12 |
Publisher | Springer VS |
Publication year | 1 Jan 2014 |
Pages | 26-37 |
ISBN (print) | 9783319084039 |
DOIs | |
Publication status | Published - 1 Jan 2014 |
Event | Scandinavian Symposium and Workshops on Algorithm Theory - Copenhagen, Denmark Duration: 2 Jul 2014 → 4 Jul 2014 Conference number: 14 |
Conference | Scandinavian Symposium and Workshops on Algorithm Theory |
---|---|
Nummer | 14 |
Land | Denmark |
By | Copenhagen |
Periode | 02/07/2014 → 04/07/2014 |
Series | Lecture Notes in Computer Science |
---|---|
Volume | 8503 |
ISSN | 0302-9743 |
See relations at Aarhus University Citationformats
ID: 81804854