On Mar 13, 2014, at 11:06 AM, Mike McFadden <[email protected]> wrote:
> Hi, I used a paper called "Ratio based in-place stable merging" to implement > a hybrid stable sort algorithm, and have been validating the results against > stable_sort and inplace_stable_sort. What's interesting is that it matches > 80-90% of the speed of stable_sort with random data, is much faster in many > other cases, and does so while using O(1) memory. Simply giving it more > memory allows it to closely match stable_sort in speed. And compared to > inplace_stable_sort it's anywhere from 3-15x faster, with random data being > about 5x faster. > > I have fully documented the algorithm and have a C++ implementation available > here: > https://github.com/BonzaiThePenguin/WikiSort > > The underlying algorithm was vetted and proven back in 2008 (there's a link > to the published paper on the GitHub project page), and the simplified > version used here is constantly tested against existing algorithms for > correctness and speed, but toying with a core feature of libc++ is obviously > not something to be taken lightly so I'm hoping for some additional vetting > and consideration. > > My ultimate goal would be to replace inplace_stable_sort at the very least, > and ideally stable_sort as well. Maybe including it as a separate sort > function for now would be wise? Mike — I apologize for not getting back to you sooner. I am quite interested in this proposal, and plan on looking at it closely … soon. Right at the moment, I’m trying to get the last few bits for full C++14 compliance done in libc++. Once that’s done, I’ll have cycles to look at this (and other things). — Marshall
_______________________________________________ cfe-commits mailing list [email protected] http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
