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. © Springer-Verlag Berlin Heidelberg 2007.
Radix Sorting With No Extra Space / Franceschini, Gianni; S., Muthukrishnan; Patrascu, Mihai. - STAMPA. - 4698:(2007), pp. 194-205. (Intervento presentato al convegno 15th Annual European Symposium on Algorithms, ESA 2007 tenutosi a Eilat; Israel nel October 8-10) [10.1007/978-3-540-75520-3_19].
Radix Sorting With No Extra Space
FRANCESCHINI, GIANNI;
2007
Abstract
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. © Springer-Verlag Berlin Heidelberg 2007.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
