Re: [boost] Taking away quicksort and mergesort

From: Sam Schetterer (samthecppman_at_[hidden])
Date: 2007-03-17 11:59:37

On March 17, Herve Bronimamm wrote     >Sam:  the Stl already implements
sorting (stable and not),  inplace and partial sorting (uses heapsort),
nth_element >(generalized median), functors and iterators (generic
interface).  As far as I can tell, your library has no added value, >except
you claim performance.  I think you might badly underestimate the effort
that goes into implementing the >C++ std library.  The only reason someone
would consider using your library over the standard library would be if >you
could convincingly and reproducingly show that you are faster (and by more
than a small percentage).  I haven't >seen numbers.

>I looked at your code and I see that you're using unguarded recursion in
quicksort (check Valois's introspective sort >revisited, published in
software practice and experience, 2000), swap in insertion sort, int instead
of ptrdiff_t (you're >going to have a bad surprise sorting 2 billion
integers on a 64bit platform), etc.  My experiences showed that radix >sort
was not faster than quicksort, due to the random access pattern (for large
arrays) and overhead of counters (for >small arrays).  And I have some
doubts about the endianness (did you test on both big and small endian
>platforms?). That's a lot of comments.  I'll leave it at that.  Cheers,
 Herve
 Well, Herve, you ask why my radixsort is better than std::sort and
std::stable_sort. It is stable, it is faster std::stable_sort, and it's
running time is O(kN), where k is the number of bytes in the object. That is
linear running time, unlike std::sort, which is O(N log N), and radixsort is
independent of the input, unlike std::sort. Finally, you can do something
called a "sort within sort" using radix quicksort, which is where you
sort by one value, than another. These "sort within sorts" are accomplished
by appending all of the bytes of your data onto a string, and these bytes
come from other strings, integers, and doubles. You then sort it with
radix_quicksort, which is incredibly high speed for strings(much faster than
std::sort and std::stable_sort). Also, I have uploaded code for radix_sort
where you can spcify starting and ending bytes, which is something that I
know that the stl does not implement.