Re: [boost] Any interest in a sorting library with a multitude of sorts?

From: Sam Schetterer (samthecppman_at_[hidden])
Date: 2007-03-15 22:39:32

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_at_[hidden]>:
   > On 3/14/07, Michael Marcin < mmarcin_at_[hidden]> 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.