Deterministic sorting in O(nlog log n) time and linear space
Y Han - Proceedings of the thiry-fourth annual ACM symposium …, 2002 - dl.acm.org
Y Han
Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, 2002•dl.acm.orgWe present a fast deterministic algorithm for integer sorting in linear space. Our algorithm
sorts n integers in the range {0, 1, 2,…, m—1} in linear space in O (n log log n) time. This
improves our previous result [8] which sorts in O (n log log n log log log n) time and linear
space. This also improves previous best deterministic sorting algorithm [3, 11] which sorts in
O (n log log n) time but uses O (m ε) space. Our results can also be compared with Thorup's
previous result [16] which sorts in O (n log log n) time and linear space but uses …
sorts n integers in the range {0, 1, 2,…, m—1} in linear space in O (n log log n) time. This
improves our previous result [8] which sorts in O (n log log n log log log n) time and linear
space. This also improves previous best deterministic sorting algorithm [3, 11] which sorts in
O (n log log n) time but uses O (m ε) space. Our results can also be compared with Thorup's
previous result [16] which sorts in O (n log log n) time and linear space but uses …
We present a fast deterministic algorithm for integer sorting in linear space. Our algorithm sorts n integers in the range {0, 1, 2, …, m—1} in linear space in O(n log log n) time. This improves our previous result [8] which sorts in O(n log log n log log log n) time and linear space. This also improves previous best deterministic sorting algorithm [3, 11] which sorts in O(nlog log n) time but uses O(mε) space. Our results can also be compared with Thorup's previous result [16] which sorts in O(nlog log n) time and linear space but uses randomization.
ACM Digital Library