Computer Science – Data Structures and Algorithms
Scientific paper
2007-06-27
Computer Science
Data Structures and Algorithms
Full version of paper accepted to ESA 2007. (17 pages)
Scientific paper
It is well known that n integers in the range [1,n^c] can be sorted in O(n) time in the RAM model using radix sorting. More generally, integers in any range [1,U] can be sorted in O(n sqrt{loglog n}) time. However, these algorithms use O(n) words of extra memory. Is this necessary? We present a simple, stable, integer sorting algorithm for words of size O(log n), which works in O(n) time and uses only O(1) words of extra memory on a RAM model. This is the integer sorting case most useful in practice. We extend this result with same bounds to the case when the keys are read-only, which is of theoretical interest. Another interesting question is the case of arbitrary c. Here we present a black-box transformation from any RAM sorting algorithm to a sorting algorithm which uses only O(1) extra space and has the same running time. This settles the complexity of in-place sorting in terms of the complexity of sorting.
Franceschini Gianni
Muthukrishnan Siddharth
Patrascu Mihai
No associations
LandOfFree
Radix Sorting With No Extra Space does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Radix Sorting With No Extra Space, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Radix Sorting With No Extra Space will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-455896