Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(4)
Linear Time
Parallel Algorithm
Randomized Algorithm
Word Length
Related Publications
(22)
Optimal bounds for the predecessor problem
Faster deterministic sorting and priority queues in linear space
Sublogarithmic Searching without Multiplications
Examining Computational Geometry, Van Emde Boas Trees, and Hashing from the Perspective of the Fusion Tree
Parallel symmetrybreaking in sparse graphs
Subscribe
Academic
Publications
Sorting in linear time?
Sorting in linear time?,10.1145/225058.225173,Arne Andersson,Torben Hagerupt,Stefan Nilsson,Rajeev Raman
Edit
Sorting in linear time?
(
Citations: 88
)
BibTex

RIS

RefWorks
Download
Arne Andersson
,
Torben Hagerupt
,
Stefan Nilsson
,
Rajeev Raman
We show that a unitcost RAM with a
word length
of bits can sort integers in the range in time, for arbitrary , a significant improvement over the bound of achieved by the fusion trees of Fredman and Willard. Provided that , for some fixed , the sorting can even be accomplished in linear expected time with a randomized algorithm. Both of our algorithms parallelize without loss on a unit cost PRAM with a
word length
of bits. The firstone yields an algorithm that uses time and op erations on a deterministic CRCW PRAM. The second one yields an algorithm that uses expected time and expected operations on a randomized EREW PRAM, provided that for some fixed . Our deterministic and randomized sequential and parallel algorithms generalize to the lexicographic sorting problem of sorting multipleprecision integers represented in several words.
Conference:
ACM Symposium on Theory of Computing  STOC
, pp. 427436, 1995
DOI:
10.1145/225058.225173
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
portal.acm.org
)
(
portal.acm.org
)
(
www.informatik.unitrier.de
)
(
doi.acm.org
)
More »
Citation Context
(46)
...In addition to the work already mentioned, many integersorting results have been published (e.g., [
5
, 47, 57, 63, 65])...
...A linear randomized time bound [
5
] is known for the case when w ≥ lg2+ε n,...
Timothy M. Chan
,
et al.
Transdichotomous Results in Computational Geometry, I: Point Location ...
...time (via radix sort [25], resp. signature sort [
6
])...
...In Appendix A, we demonstrate this for the (comparatively simple) O(n log logn) sorting algorithm by Andersson et al [
6
]...
Kevin Buchin
,
et al.
Delaunay Triangulations in O(sort(n)) Time and More
...Consequently it has been used in various algorithms [8,
3
, 12, 11, 10]...
Johannes Schneider
,
et al.
A logstar distributed maximal independent set algorithm for growthbo...
...packed sequences by Andersson et al. [
3
] which we review first...
...Lemma 8 (Andersson et al. [
3
]) We can compact an fpacked sequence of length s stored in O(1) words in time O(log s)...
Philip Bille
.
Faster Approximate String Matching for Short Patterns
...This can be done in O(1) time using standard techniques [25, 15,
3
], provided we have available the integer constant k that contains 1s in bit positions 0, b,2b, . . . , b � ⌊ (lg n ∗ )/b⌋, as well as tables that enable us to compute, for every integer x of lg n ∗ or fewer bits, the index of the...
Rajeev Raman
,
et al.
Succinct Indexable Dictionaries with Applications to Encoding $k$ary ...
References
(34)
Introduction to parallel algorithms and architectures: arrays
(
Citations: 785
)
F. T. Leighton
Published in 1993.
Surpassing the Information Theoretic Bound with Fusion Trees
(
Citations: 187
)
Michael L. Fredman
,
Dan E. Willard
Journal:
Journal of Computer and System Sciences  JCSS
, vol. 47, no. 3, pp. 424436, 1993
When can we sort in o(n log n) time?
(
Citations: 7
)
Amir M. Benamram
,
Zvi Galil
Conference:
IEEE Symposium on Foundations of Computer Science  FOCS
, pp. 538546, 1993
Optimal parallel string algorithms: sorting, merging and computing the minimum
(
Citations: 5
)
Torben Hagerup
Conference:
ACM Symposium on Theory of Computing  STOC
, pp. 382391, 1994
Decision trees and random access machines
(
Citations: 51
)
J. Simon
,
W. J. Paul
Published in 1982.
Sort by:
Citations
(88)
Delaunay triangulations in O (sort( n )) time and more
Kevin Buchin
,
Wolfgang Mulzer
Journal:
Journal of The ACM  JACM
, vol. 58, no. 2, pp. 127, 2011
Counting Inversions, Offline Orthogonal Range Counting, and Related Problems
(
Citations: 2
)
Timothy M. Chan
,
Mihai Patrascu
Conference:
ACMSIAM Symposium on Discrete Algorithms  SODA
, pp. 161173, 2010
Transdichotomous Results in Computational Geometry, I: Point Location in Sublogarithmic Time
(
Citations: 7
)
Timothy M. Chan
,
Mihai Patrascu
Journal:
Siam Journal on Computing  SIAMCOMP
, vol. 39, no. 2, pp. 703729, 2009
Delaunay Triangulations in O(sort(n)) Time and More
(
Citations: 3
)
Kevin Buchin
,
Wolfgang Mulzer
Conference:
IEEE Symposium on Foundations of Computer Science  FOCS
, pp. 139148, 2009
A logstar distributed maximal independent set algorithm for growthbounded graphs
(
Citations: 47
)
Johannes Schneider
,
Roger Wattenhofer
Conference:
Symposium on Principles of Distributed Computing  PODC
, pp. 3544, 2008