TY - GEN
T1 - Radix sorting with no extra space
AU - Franceschini, Gianni
AU - Muthukrishnan, S.
AU - Pǎtraşcu, Mihai
N1 - Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.
PY - 2007
Y1 - 2007
N2 - It is well known that n integers in the range [1, nc] 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√log log n) time [5]. 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.
AB - It is well known that n integers in the range [1, nc] 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√log log n) time [5]. 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.
UR - http://www.scopus.com/inward/record.url?scp=38049066452&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=38049066452&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-75520-3_19
DO - 10.1007/978-3-540-75520-3_19
M3 - Conference contribution
AN - SCOPUS:38049066452
SN - 9783540755197
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 194
EP - 205
BT - Algorithms - ESA 2007 - 15th Annual European Symposium, Proceedings
PB - Springer Verlag
T2 - 15th Annual European Symposium on Algorithms, ESA 2007
Y2 - 8 October 2007 through 10 October 2007
ER -