Radix Sorting With No Extra Space
| dc.creator | Franceschini, Gianni | |
| dc.creator | Muthukrishnan, S. | |
| dc.creator | Patrascu, Mihai | |
| dc.date | 2007-06-27 | |
| dc.date.accessioned | 2026-07-07T08:12:50Z | |
| dc.date.available | 2026-07-07T08:12:50Z | |
| dc.description | 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. | |
| dc.description | Full version of paper accepted to ESA 2007. (17 pages) | |
| dc.identifier | https://arxiv.org/abs/0706.4107 | |
| dc.identifier | http://arxiv.org/abs/0706.4107 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/132591 | |
| dc.subject | Data Structures and Algorithms | |
| dc.title | Radix Sorting With No Extra Space | |
| dc.type | text |