How to modify counting sort so that it sorts the elements in place,
i.e. using extra amount of memory that is constant and independent of
the size of the input.

"Ravi" <ra.ravi.rav@gmail.com> wrote in message 
news:1188561683.635564.152710@i13g2000prf.googlegroups.com...
> How to modify counting sort so that it sorts the elements in place,
> i.e. using extra amount of memory that is constant and independent of
> the size of the input.
>

come up with some 'sane' maximum and use that (pre-allocated buffers).
switch to a different sort algo.
....

in-place output:
harder, since this algo does not fill linearly.

one possibility is that for each element we add to a spot, we exchange it 
with the value already there, and continue on from this spot (marking sorted 
spots somehow). if this spot is the target (the item is in place), we mark 
this spot and move on to the next (unmarked) spot. by the time we reach the 
end of the buffer, everything should be sorted (at least value-wise, but may 
not be sufficient is item identity is of much concern).

or such...