2 papers
cs.DS2007
Radix Sorting With No Extra Space
Gianni Franceschini, S. Muthukrishnan, Mihai Patrascu
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…
cs.DS2003
An In-Place Sorting with O(n log n) Comparisons and O(n) Moves
Gianni Franceschini, Viliam Geffert
We present the first in-place algorithm for sorting an array of size n that performs, in the worst case, at most O(n log n) element comparisons and O(n) element transports. This so…