Re: [boost] [sorting] Taking away quicksort and mergesort

From: Herve Bronnimann (hervebronnimann_at_[hidden])
Date: 2007-03-17 12:02:36

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
--
Hervé

Sent from my BlackBerry® wireless handheld  
Please excuse misspellings and typos  

-----Original Message-----
From: Sam Schetterer <samthecppman_at_[hidden]>
Date: Fri, 16 Mar 2007 22:06:36 
To:boost <boost_at_[hidden]>
Subject: [boost] [sorting] Taking away quicksort and mergesort

Would users care if I took quicksort and merge sort out of the library? They
are already implemented by the stl.
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost