On March 14, 2007, Ben Bear wrote:

I'm care for how many times of collecting the radix sort needed while sort some very long string, such as "012..9abc..zABC..Z".

2007/3/14, Giovanni Piero Deretta < gpderetta@gmail.com>: On 3/14/07, Michael Marcin < mmarcin@method-solutions.com> wrote:

...

Giovanni Piero Deretta wrote:

...

Isn't sort + stable sort enough?

Do we really need specialized interfaces for these?

I for one would like a generic radix sort where I could specify the number of bits to grab and where in a UDT to grab each bit or a range of bits from.

Do you really see no use for a O(n) sorting algorithm?

I was speaking about the various "reverse sort", "sort by field", "sort by two fields" etc. I definitely think that a radix sort would be useful.

gpd _______________________________________________ To answer your question, "Three-way radix quicksort uses 2N ln N byte comparisons, on the average, to sort N (arbitraily long) keys."(Sedgewick 446). There is your answer. The running time of radix quicksort is k + 2N ln N, where N is the number of keys, and k is the number of bytes. Normal quicksort has a running time of k(2N ln N), with the same variables. To answer your question for radix sort, you would not use it for strings. If you did, however, then the number of collection times would be kN, where k is the number of bytes and N is the number of items.